956 Redu

[•bogdan2412]

Aici puteti discuta despre problema Redu.

[•popoiu.george]

Cod:

for(int t=1;t<=N-1;t++)
    {
    for(int i=1;i<=N-t;i++)
        {
        int j=i+t;
        if(i+1==j)cmin[i][j]=c[s[i]][s[j]];
        else
            {
            cmin[i][j]=PINF;
            if((j-i+1)%2==0)
                for(int k=i+1;k<=j;k++)
                    {
                    if( (k-i-1)%2==0 && (j-k)%2==0)
                    if(cmin[i][j]>cmin[i+1][k-1]+cmin[k+1][j]+c[s[i]][s[k]])cmin[i][j]=cmin[i+1][k-1]+cmin[k+1][j]+c[s[i]][s[k]];
                    }
            }
        }
    }

Acum testez daca secventa de la (i+1,k-1) are lungime para si daca cea de la (k+1,j) are de asemenea lungime para si am modificat totul pe int si iau 70p cu incorect pe ultimele 3 teste.
Este ceva ce imi scapa? Trebuie facuta vreo initializare anume?


S-a rezolvat, am luat 100. Problema era ca aveam dimensiunea matricii fix cat imi trebuia, si erau situatii k+1>j si nu mai aveam loc   De acuma o sa ma invat minte sa declar un pic mai mult decat am nevoie, sa nu declarati fix cat e limita !

[edit] modifica-ti measjele anterioare!

[•ParaipaN]

Incercai o solutie recursiva si iau 50p. Idei de imbunatatire?

[•wefgef]

Incercai o solutie recursiva si iau 50p. Idei de imbunatatire?

Offtopic: Da, ai putea sa folosesti perfectul compus .

[•ParaipaN]

Ok, atunci, AM INCERCAT o solutie recursiva, si iau 50p. Alte idei de imbunatatire?

[•freak93]

Problema nu e ca faci recursiv. Problema e ca sursa ta ajunga sa faca backtracking. Fa matricea de 26 pe 26 numai 0 si pune n cam 50 sa vezi cum merge la tine.
Ce faci tu in sursa ta se cheama memoizare si in general e un procedeu bun(se comporta mai bine ca solutile iterative de multe ori). Problema e ca valoarea pe care o folosesti ca sa iti dai seama ca nu ai calculat inca acea valoarea e 0 la tine. Si 0 poate fi un raspuns.