z-dance

Pretpostavljam da je matching... koliko sam u pravu?

nisi u pravu..Cisto dinamicko..Razmisli malo, pa ako ne dodjes do ideje , pitaj.

Hvala.

Javim se ako ne skuzim.

Neznam zasto ali mi ovaj zadatak puca na tri test primjera(javlja krivo rjesenje)

Ja sam radio rekurzivno sa memoizacijom:
Koji slucaj sam zaboravio u formuli?

int N, M;
int adj[1005][1005] = { 0 };
int memo[1005][1005];

int rec( int boy, int girl ) {
	if( boy == N ) return 0;

	int ret = 0;
	for( int i = girl; i < M-(N-boy-1); ++i ) {
		if( memo[boy+1][i+1] != -1 )
			ret >?= adj[boy][i] + memo[boy+1][i+1];
		else
			ret >?= adj[boy][i] + rec( boy+1, i+1 );
	}
	return memo[boy][girl] = ret;
}

int main() {
	scanf( "%d %d", &amp;N, &amp;M );
	for( int i = 0; i < N; ++i )
		for( int j = 0; j < M; ++j ) {
			scanf( "%d", &amp;adj[i][j] );
			memo[i][j] = -1;
		}

	printf( "%d\n", rec( 0,0 ) );
	return 0;
}

Jel mogu da dobijem 6. test primer? :)
Tnx :)

reci mail.dosta zauzima..

@relja
tnx
@svi modovi & admin :)
izbacite ovaj deo u textu da je svaki element matrice manji od 32000, meni se program tu sapleo :)

Imam 2 pitanja :
(1)
Matrica treba biti 1000 x 1000 , i to daje mi daje run-time error na dev-c++ compileru. Dali bi 1000x1000 matrica prosla na z-treningu?
Naravno od tipa int.

(2)
Dali zbir elemenata u bilo kom primeru moze da nadmasi int ?
Ja mislim da je int -32000..+32000 .

[quote author=Sanja Popovic link=topic=10229.msg11891#msg11891 date=1178016472]
@svi modovi & admin :)
izbacite ovaj deo u textu da je svaki element matrice manji od 32000, meni se program tu sapleo :)
[/q]

[q]Dali zbir elemenata u bilo kom primeru moze da nadmasi int ?
Ja mislim da je int -32000..+32000 .[/q]

Drz' se ti longinta, ma sta pisalo u textu :)

Ok tako sam i mislio .
TNX

Moze li 5ti test primer?

Imam ideju za ovaj zadatak sto mislim da je dobra , ali izgleda da sam propustio nek i slucaj pa ako moze mala pomoc. (prolazi na 1,2,3,4 i 6 test primer) .



Ovo je osnova:

dp[1][j]=max(dp[1][j-1],svidja[1][j]);

I onda:

if(j>=i)
  dp[i][j]=dp[i-1][j-1] + svidja[i][j] ;  // za svako i(2,N), j(1,M)

I na kraju najdem najvece od dp[N][j] // za svako j(1,M)


Sta sam propustio?

Neko da mi odgovori? ??? ??? ???

Molim nekog ko je resio ovaj zadatak da mi kaze gde gresim?

Ja mislim da ti je inicijalizacija DP-a dobra, ali glavna petlja nije.

dp[i][j] = max( dp[i][j-1] , dp[i-1][j-1]+svidja[i][j] );

Probaj ovo, pa vidi jel prolazi...

I jedno pitanje: zasto indeksiras od jedinice a radis u C-u? Navika ili...

I da, umalo da zaboravim...

Ako onako ispises DP, tada nema potreba da trazis maksimum u N-toj vrsti. Resenje ti se nalazi u polju dp[N-1][M-1], ili u tvom slucaju dp[N][M].

Javi kako je proslo.

Evo sad cu da probam to sto kazes pa da vidimo.
Inace indeksiram od 1 zato sto sam cesto pravio greske kad sam koristio array od 0 do n-1 . Cesto mi se desavalo da napisem array[n] (a tog polja nema ili ima neku random vrednost)i da ne mogu da nadjem gresku.
Sad mi to vise nije problem ali ostalo je u navici :D.