PD

[•paliuca]

Salut,I need some help 

Se dau doua cuvinte , primul are pentru fiecare litera un cost asociat.
Se cere subsirul comun de cost maxim..Any ideea ?

[•sigrid]

Salut  .

In primul rand daca toate costurile sunt pozitive, atunci e logic ca subsirul de cost maxim va fi cel mai lung subsir comun. Pentru a rezolva problema asta te sfatuiesc sa rezolvi mai intai http://infoarena.ro/problema/cmlsc din arhiva educationala.

Daca pot exista si costuri negative atunci te sfatuiesc (desi trebuie sa-ti spun ca n-am implementat) ca in matricea de lungimi sa retii de fapt costurile, adica a[k][j]= cel mai mare cost al unui subsir utilizand primele k litere din primul sir si primele j litere din al doilea.

Ar trebui sa mearga. Spor la treaba

[•paliuca]

Salut  .

In primul rand daca toate costurile sunt pozitive, atunci e logic ca subsirul de cost maxim va fi cel mai lung subsir comun. Pentru a rezolva problema asta te sfatuiesc sa rezolvi mai intai http://infoarena.ro/problema/cmlsc din arhiva educationala.

Si daca sunt mai multe subsiruri comune de lungime maxima cum sti sa-l iei cel mai mare ?

[•devilkind]

In primul rand daca toate costurile sunt pozitive, atunci e logic ca subsirul de cost maxim va fi cel mai lung subsir comun. Pentru a rezolva problema asta te sfatuiesc sa rezolvi mai intai http://infoarena.ro/problema/cmlsc din arhiva educationala.

nu e chiar asa. Pica pe urmatorul test.

aba
ab

Costurile sunt : a->1 b->1 a->100
Subsirul de lungime maxima o sa fie "ab" si o sa aibe cost 2, insa subsirul de cost maxim este "a" si are costul 100.

[•byndrsn]

Probabil ca fiecare litera are cost unic (altfel problema nu e bine definita, de ex ab poate avea cost 101). Un exemplu mai clar e bacd, adb cu costuri b : 100, a, c, d : 1. Ideea de DP e foarte similara totusi.

[•paliuca]

Nu sunt neaparat distincte costurile.
So, any solution ?

[•devilkind]

deci cum e pana la urma?? dane un exemplu cum asociezi costurile alea??

[•paliuca]

primul sir : XYXYX
costuri : 2 2 7 1 1
second :   XY

Solutia e XY cu costul 8 de pe penultimele 2 pozitii din primul sir

[•byndrsn]

Pai cam aceeasi solutie ca si pentru subsirul de lungime maxima.

Mai precis, fie s = s_1 .. s_n si t = t_1 .. t_m sirurile initiale. Fie din[ i ][ j ] = costul maxim al unui subsir al sirurilor s_1 .. s_i si t_1 .. t_j. O recurentza e cam asa (cred):

din[ i ][ 0 ] = din[ 0 ][ j ] = 0
din[ i ][ j ] = max(0, din[ i - 1 ][ j - 1 ] + cost(s_i), din[ i ][ j - 1 ], din[ i - 1 ][ j ]), daca s_i = t_j
           = max(0, din[ i ][ j - 1 ], din[ i - 1 ][ j ]), altfel

N.B.: ma refeream la faptul ca daca o litera nu are cost unic, notiunea de cost al unui subsir nu e bine definita.

Later edit: OK, mi-am dat seama ce vrei sa spui.

[•paliuca]

Are vreun rost sa-l pui si pe 0 cand faci maximul  ?

[•byndrsn]

Nu e necesar sa pui 0.