infoarena informatica de performanta

Jetoane2

Problema se rezolva prin programare dinamica. Vom considera 2 matrici:

• A_{i, j} = 1 daca intervalul de jetoane dintre pozitiile i si j poate fi eliminat, sau 0, altfel.
• B_{i, j, k} = 1 daca intre pozitiile i si j se poate plasa al k-lea cuvant si se poate elimina tot intervalul, sau 0, altfel.

Astfel B_{i, j k} = 1 daca si numai daca exista un p ∈ [i, j], astfel incat:

1. Cuv_{k, l} = Sir_p+l, ∀ 1 ≤ l ≤ Lung_k
2. A_{i, p-1} = A _{(i+Lung{k}) , j} = 1

Sir_p+l reprezinta sirul initial, Cuv_{k, l} reprezinta a l-a litera din al k-lea cuvant si Lung_k, lungimea acestuia. Dinamica se va calcula, crescator, dupa lungimea intervalului [i, j]. Daca ∃ k astfel incat B_{i, j, k} = 1, atunci A_{i, j} = 1.

Dupa determinarea valorilor lui A si cum scorul depinde exclusiv de intervalele [i, j] ce pot fi eliminate, se va aduna la rezultat suma ponderilor de pe toate intervalele [i, j] cu A_{i, j} = 1.

Complexitatea solutiei este O(N * L³ * CONST), unde L reprezinta lungimea sirului initial, iar CONST = 10.

Exista si o solutie de complexitate O(N * L³), care, in practica, merge mai repede. Aceasta solutie a fost data de catre Cosmin Gheorghe si o voi publica imediat dupa ce primesc acordul sau.