Imprimă pagina - 956 Redu

Titlul: 956 Redu
Scris de: Bogdan-Cristian Tataroiu din Decembrie 20, 2009, 14:49:47

Aici puteti discuta despre problema Redu (http://infoarena.ro/problema/redu).

Titlul: RÄƒspuns: 956 Redu
Scris de: George Popoiu din Decembrie 22, 2009, 17:34:21

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 ! :ok:

[edit] modifica-ti measjele anterioare!

Titlul: RÄƒspuns: 956 Redu
Scris de: Paraipan Jr. din Septembrie 16, 2012, 16:57:22

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

Titlul: RÄƒspuns: 956 Redu
Scris de: Andrei Grigorean din Septembrie 16, 2012, 21:39:46

Citat din mesajul lui: Paraipan Jr. din Septembrie 16, 2012, 16:57:22

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

Offtopic: Da, ai putea sa folosesti perfectul compus :P.

Titlul: RÄƒspuns: 956 Redu
Scris de: Paraipan Jr. din Septembrie 17, 2012, 06:50:11

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

Titlul: RÄƒspuns: 956 Redu
Scris de: Adrian Budau din Septembrie 17, 2012, 09:02:02

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.

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Bogdan-Cristian Tataroiu din Decembrie 20, 2009, 14:49:47