SumDif

[•chera_lary]

Salut! Voi ce recurenta ati da la problema SumDif http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=117 de pe .Campion.
Ideea mea este sa generez toate sumele formate din k elemente (pe baza programarii dinamice) si apoi sa calculez diferenta maxima prin alegerea pe rand a fiecarei sume obtinute si scazand din ea cele mai mici valori nealese!
Metoda greedy nu ma intereseaza!

[•wefgef]

C[ i ][ j ] = Valoarea maxima pe care o poti obtine punand in prima grupa j cartonase dintre primele i. Complexitatea este N^2.

[•chera_lary]

Multumesc pentru raspuns, deja am apucat sa scriu o dinamica care am observat ca rezolva corect, complexitatea de timp in cazul cel mai nefavorabil este O(N^3), insa ce ma intereseaza cel mai mult este complexitatea de spatiu, primesc killed by signel 11;

Sol[ i ][ j ] = valoarea maxima dintre diferenta sumelor celor doua submultimi daca cardinalul primei multimi este i si se adauga la suma maxima obtinuta la pasul i-1 cartea j (in prima multime);
Cartea j se va adauga in urmatorul mod:
La suma maxima accesibila de la pasul i-1 adunam minimul cartii (deoarec acesta a fost scazut la pasul anterior) si valoarea maxima de pe carte!
Matricea s are rolul de a retine ce carti au fost utilizate pentru a obtine suma maxima utilizand cartea j.

Am sa incerc sa implementez si recurenta ta, dar m-ar interesa daca ati reusi sa modificati si dinamica mea (in cazul in care se poate)!

Cod:

...
typedef struct
{
	int f1;
	int f2;
}Elem;

Elem C[nMax];
int Sol[1][nMax];
bool s[1][nMax][nMax];

void solve()
{
	for(int i=1;i<=n;i++)
	{
		Sol[0][i] = max(C[i].f1, C[i].f2);
		s[0][i][i] = true;
		for(int j=1;j<=n;j++)
			if(j==i) continue;
			else Sol[0][i] -= min(C[j].f1, C[j].f2);
	}
	for(int i=1;i<k;i++)
		for(int j=1;j<=n;j++)
		{
			int maximum=-1000000, indx;
			for(int l=1;l<=n;l++)
				if(l==j) continue;
				else if(maximum<Sol[(i-1)%2][l])
				{
					maximum=Sol[(i-1)%2][l];
					indx=l;
				}
			
			int max1, min1;
			if(C[j].f1<C[j].f2) min1 = C[j].f1, max1 = C[j].f2; else min1 = C[j].f2, max1 = C[j].f1;
			
			for(int l=1;l<=n;l++) s[i%2][j][l] = s[(i-1)%2][indx][l];
			if(!s[i%2][j][j]) Sol[i%2][j] = maximum + min1 + max1, s[i%2][j][j] = true; else Sol[i%2][j] = -1000000;
		}
}

...

Da! Mi-am dat seama ca depasesc si timpul, sursa obtine 50 de puncte.