Titlul: RV
Scris de: CHERA Laurentiu din Octombrie 23, 2010, 18:35:36
Salut! La problema RV (http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=100 (http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=100)) am dedus urmatoarea recurenta: 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!
Titlul: Răspuns: RV
Scris de: Florian Marcu din Octombrie 23, 2010, 19:27:08
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 ).
Titlul: Răspuns: RV
Scris de: CHERA Laurentiu din Octombrie 23, 2010, 19:45:08
Pai da dar forul cu n este in interiorul forului cu k; 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! 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';
}
}
}
|