deci pt exemplul de la problema as obtine ceva de genu

Cod:

5 4 3 4 3 2 1 2 3 4 
4 3 2 3 2 1 0 1 2 3 
3 2 1 2 3 2 1 2 3 4 
2 1 0 1 2 1 0 1 2 3 
1 -1 1 2 2 2 1 2 3 4 
0 -1 2 2 1 2 2 3 4 5 
-1 3 2 1 0 1 2 3 4 5 
5 4 -1 -1 -1 -1 3 4 5 6 
6 5 6 7 6 5 4 5 6 7 
7 6 7 8 7 6 5 6 7 8 

unde a(i,j) = dist minima pana la cel mai apropiat dragon. iar a(i)(j)=-1 unde avem zid
e corect?

Deci dragonul nu poate da cu flacari decat in S,N,E,V ,corect?. deci daca am avea

Cod:

5 5
0....
..I..
...D.
.....
.....

atunci distanta ar fi infinit.... pt ca paftenie nu interactioneaza cu dragonul...nu?, in cazul acesta ce afisez?

Daca avem

Cod:

5 5
I....
*....
D....
.....
...0.

at distanta minima este 2? Sau zidul "blocheaza" dragonul?

Of...si ai luat 100?...am facut sursa de 100 in sfarsit si mie imi da 1140

Pt

Cod:

 
5 5 10
0 0 0 0 0
0 2 0 3 0
0 0 1 0 0
0 2 0 0 0
0 0 0 0 0
1 1 3 3

va da 2580? Ms anticipat

As vrea sa stiu daca a reusit cineva sa gaseasca singur formula pt aceasta problema, m-am uitat pe sol oficiala si mi se pare fff greu de dedus

poate am inteles eu gresit ce zice acolo....
LE: am rezolvat-o pana la urma

m-am uitat, am facut ca acolo si tot nu iese

nu-mi iese deloc lungimea minima lexicografica

Cod:

# for(i=n-1;i>=1;i--){  
#         min=l[i]=INF;  
#         for(j=i+1;j<=n;j++){  
#                 if(v[j]>=v[i] && v[j]<min){  
#                         min=v[j];  
#                         if(l[j]+1<l[i]){  
#                             l[i]=l[j]+1;  
#                             p[i]=j;  
#                         }  
#                         else if(l[j]+1==l[i])  
#                             if(v[j]<v[p[i]])  
#                                 p[i]=j;  
#                     }  
#                 if(v[j]>=v[i])   
#                     ok[j]=1;  
#         }  
#         if(l[i]==INF) l[i]=1; 

unde gresesc?

Intai vreau sa nu mai iau wa, apoi vad eu cum fac cu sirul lexicografic, asta ar trebui sa-mi iasa....am modificat putin sursa dar tot nu iese

Cod:

for(i=n-1;i>=1;i--){
		min=l[i]=INF;
		for(j=i+1;j<=n;j++){
				if(v[j]>=v[i] && v[j]<min){
						l[i]=l[j];
						min=v[j];
						p[i]=j;
					}
				if(v[j]>=v[i]) 
					ok[j]=1;
		}
		if(l[i]==INF) l[i]=0;
		l[i]++;
	}

daca gasesc un v[j]<min nici nu ma mai intereseaza ce lungime are l(j),il iau automat pe ala pt ca e cel bun. Fie urmatoarele 2 cazuri:
........7 3 4 9 9 10......      - presupunem ca v(i)=7; cand caut un j minim il gases pe primul 9 care e mai lung dar e corect, apoi daca l-as lua pe al 2lea 9 il iau pe acesta in considerare , si ar veni subsirul" 7 9 10" dar este gresit pt ca poate fi extins cu primul 9.

.......7 2 3 9 11 13 9       - v(i)=7. acum e corect sa-l iau tot pe primul 9(subsirul format ar fi 7 9 9)
=> nu ma intereseaza daca gasesc un alt v(j)==min

...dupa lupte seculare tot nu mi-a iesit ...imi mai poti da niste indicii?

Wow...am inteles...multumesc tuturor

LE:

tot nu-mi iese aceasta problema. m-am uitat si pe sol oficiale , am facut ca acolo si tot nu e bine...

Cod:

l[n]=1;
	for(i=n-1;i>=1;i--){
		min=l[i]=INF;
		for(j=i+1;j<=n;j++){
				if(v[j]>=v[i] && l[j]<l[i] && v[j]<min){
					l[i]=l[j];
					min=v[j];
					p[i]=j;
				}
				if(v[j]>=v[i]) 
					ok[j]=1;
		}
		if(l[i]==INF) l[i]=0;
		l[i]++;
	}
min=INF;
	for(i=1;i<=n;i++)
		if(l[i]<min && !ok[i]){
			min=l[i];
			poz=i;
		}
....

l(i) = lungimea minima a unui subsir cresc maximal care incepe de pe pozitia i
p() = poz(pt reconstituire)
ok(i) = 1 daca subsirul care incepe de pe poz i poate fi lipit cu cineva din stanga, si 0 in caz contrar.

Va puteti da seama unde am gresit? Multumesc anticipat

Aha , am inteles, multumesc, dar cum ramane cu cel mai scurt subsir crescator maximal , asta ce inseamna?

Nu prea inteleg cerinta problemei si nici explicatiile de la restrictii..care este diferenta intre un subsir crescator si un subsir crescator maximal ? si ce conditie trebuie sa respecte un subsir crescator maximal ca sa fie mai mic decat altul ?   multumesc anticipat

Am trimis o sursa goala doar cu citire + qsort...si am luat ca timp +300ms....umpic cam nasol... zice-ti-mi si mie o sortare mai buna, si sa ma ajutati sa o implementez, va rog(PM daca se poate)

Nu stiu daca ai rezolvat-o intre timp dar uite o idee: i-ati matricea b(i)(j)=suma maxima care se poate obtine pornind de pe pozitia (i,j)

Nu am vrut decat sa ajut... ....oricum si metoda cu aria e destul de clar explicata ...daca e prea detaliat, rog un admin sa-mi stearga postul

Editat de moderator: Nu postati rezolvari complete! Mai ales cand nu vi le cere nimeni!

pf...am scris gresit. nu iau 2 tle, iau 2 wa:D

Hai mai chiar nu stie nimeni?

LE: M-am uitat si la solutiile oficiale, dar nu am inteles ce sa fac cu acel vector H si ce intrebuintare are

LLE: Never mind! am rezolvat-o

Eu am rezolvat problema cu 2 foruri ...destul de simpla ideea , dar iau 80 de pcte cu 2 *wa. Am luat un for i=1,n presupunand ca pretul pus de vanzator este pret(i) ; dupa am luat for j=1,n si am facut subsecventa de suma maxima( neuitand sa-l platesc si pe vanzator) ....mai exact

Cod:

for(i=1;i<=n;i++){
		s=0;
		poz=1;
		if(v[i].b-c>max) max=v[i].b-c;
		for(j=1;j<=n;j++){
			if(v[j].b>=v[i].b) s+=v[i].b;
			if(s-( v[j].a - v[poz].a + 1)*c>max) 
				max=s-(v[j].a-v[poz].a+1)*c;
			if(s-(v[j].a-v[poz].a+1)*c<0) { s=0; poz=j+1; }
		}
	}

imi poate spune si mie cineva unde am gresit? sau sa-mi dea un exemplu pe care nu functioneaza acest algoritm? multumesc anticipat

Go go go!

scuze ca postez aici, dar nu prea as avea unde in alta parte, rog mult pe cineva sa puna problemele de la OJI 2008 cls a9a pe arhiva

La "probleme care se pot rezolva cu generare de combinari" puteti adauga problema reteta.

Poate sa-mi dea si mie cineva un test mai "dracos" poate ma prind si eu de ce gresesc si iau doar 30 de p.

Later Edit: Nu conteaza am rezolvat, problema era ca nu imi iesea bine subsirul in caz ca aveam si 0 printre acele numere
PS: am descoperit si ce are testul 9, dar nu voi dezvalui pt ca nu mai are niciun farmec daca nu faci singur. Hint: celor care nu v-a iesit incercati niste teste mici.

Vedeti ca s-a blocat evaluatorul la Dorin Oltean

Cod:

Eu am facut un fill pt [i][j] cu a[i][j]=0 incepand cu pozitia (1,1), si am pus a[i][j]=-1; apoi am
 facut al doilea fill cand parcurgeam matricea si gaseam un lac(1), si faceam 
fill cat timp  a[x][y] !=-1; 

Pe testele mele imi merge bine , dar iau doar 80 de pcte, ar putea sa-mi dea cineva un test care sa-mi ateste metoda?

Later Edit: am rezolvat-o pana la urma