RV

[•chera_lary]

Salut!
La problema RV (http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=100) am dedus urmatoarea recurenta:

Cod:

A[0][n-k][n] = min(s[n-k] + A[1][n-k+1][n], s[n] + A[1][n-k][n-1]);
A[1][n-k][n] = max(s[n-k] + A[0][n-k+1][n], s[n] + A[0][n-k][n-1]);

A[x][y][z] = sirul obtinut daca muta jucatorul x+1 cu sirul de la poz y la poz z pe tabla rosie!
s[n] = sirul aflat initial pe tabla rosie!

Recurentele functioneaza perfect, in offline obtin 100 de puncte, insa pe evaluatorul online depasesc spatiul de memorie!

[•Florian]

Din cate vad eu, poti renunta la a treia dimensiune, retinand in schimb doua matrice ( ca ai nevoie doar de n - 1 ca sa calculezi pentru n ).

[•chera_lary]

Pai da dar forul cu n este in interiorul forului cu k;

Cod:

int len = strlen(tr);
for(int l=1;l<len;l++)
{
	for(int i=0;i<len-l;i++)
	{
		res1[1] = '\0'; res2[1] = '\0';
		res1[0] = tr[i];
		strcat(res1, sol[0][i+1][i+l]);
		res2[0] = tr[i+l]; 
		strcat(res2, sol[0][i][i+l-1]);
		strcpy(sol[1][i][i+l], minimum(res1, res2));
			
		res1[1] = '\0'; res2[1] = '\0';
		res1[0] = tr[i];
		strcat(res1, sol[1][i+1][i+l]);
		res2[0] = tr[i+l]; 
		strcat(res2, sol[1][i][i+l-1]);
		strcpy(sol[0][i][i+l], maximum(res1, res2));
	}
}

LE: Am rezolvat! Am alocat matricea dinamic!

Cod:

void alocare()
{
	//sol = new char[2][nMax][nMax][nMax];
	int len = strlen(tr)+1;
	
	sol = new char***[2];
	for(int i=0;i<2;i++)
	{
		sol[i] = new char**[len];
		for(int j=0;j<len;j++)
		{
			sol[i][j] = new char*[len];
			/*for(int k=0;k<len;k++)
				sol[i][j][k] = new char[k],
				sol[i][j][k][1] = '\0';*/
		}
	}
	
	for(int i=0;i<len;i++)
	{
		for(int j=0;j<len-i;j++)
		{
			sol[0][j][j+i] = new char[i];
			sol[0][j][j+i][1] = '\0';
			
			sol[1][j][j+i] = new char[i];
			sol[1][j][j+i][1] = '\0';
		}
	}
}