*Subproblema 1*

Aceasta problema admite mai multe solutii, insa cea de complexitate optima se foloseste de un automat 'Aho-Corasick':http://www.infoarena.ro/problema/ahocorasick. Va rugam sa-l studiati inainte de a citi mai departe. Vom numi nod terminal un nod din Aho-Corasick in care se termina un cuvant din dictionar. Fiecare nod din automat va avea un vector dinamic $mathces$, o lista cu indici ai prefixelor din text pentru care cuvantul determinat de acest nod (mai precis de drumul de la radacina la acest nod) este sufix. Atunci cand 'trecem textul prin automat' incarcam fiecare indice i din text (care reprezinta prefixul care se termina la pozitia i) in vectorul $matches$ al nodului la care am ajuns la momentul respectiv. Acesta va fi cel mai lung prefix al unui cuvant din dictionar care este sufix al prefixului i al sirului. Pentru a afla toate prefixele din dictionar care sunt sufixe ale acestui prefix i, este suficient sa copiem continutul vectorului $matces$ al nodului curent in vectorii $matches$ ai nodurilor in care ajungem urmarind pointerul de nepotrivire _fail_. Putem scoate pozitiile de potrivire ale cuvintelor din vectorii _matches_ ale nodurilor terminale.

Aceasta problema admite mai multe solutii, insa cea de complexitate optima se foloseste de un automat 'Aho-Corasick':http://www.infoarena.ro/problema/ahocorasick. Va rugam sa-l studiati inainte de a citi mai departe. Vom numi nod terminal un nod din Aho-Corasick in care se termina un cuvant din dictionar. Fiecare nod din automat va avea un vector dinamic $mathces$, o lista cu indici ai prefixelor din text pentru care cuvantul determinat de acest nod (mai precis de drumul de la radacina la acest nod) este sufix. Atunci cand 'trecem textul prin automat' incarcam fiecare indice i din text (care reprezinta prefixul care se termina la pozitia i) in vectorul $matches$ al nodului la care am ajuns la momentul respectiv. Acesta va fi cel mai lung prefix al unui cuvant din dictionar care este sufix al prefixului i al sirului. Pentru a afla toate prefixele din dictionar care sunt sufixe ale acestui prefix i, este suficient sa copiem continutul vectorului $matces$ al nodului curent in vectorii $matches$ ai nodurilor in care ajungem urmarind pointerul de nepotrivire _fail_. Apoi, putem scoate pozitiile de potrivire ale cuvintelor din vectorii _matches_ ale nodurilor terminale.

Atentie ! Aici se poate cadea intr-o capcana. Problema garanteaza ca numarul de aparitii ale cuvintelor din dictionar in text nu depaseste 10^4^, dar problema nu garanteaza pentru numarul de aparitii ale prefixelor cuvintelor din dictionar.

Problema aceasta se trateaza prin programare dinamica. Este clar ca putem inlatura intervalele care contin alte intervale. Dinamica de mai jos functioneaza si daca nu facem aceasta reducere, dar o sa consideram ca o facem pentru ca simplifica explicatia:

Intervalele sunt acum lipsite de parantezari deci o sortare dupa capatul stanga reprezinta si o sortare dupa capatul dreapta. Indexam intervalele dupa aceasta ordine. Al i-lea interval este cel cu al i-lea capat stanga. Deoarece alegand o pozitie i din text acoperim o secventa continua de astfel de intervale, putem construi dinamica:

Intervalele sunt acum lipsite de parantezari deci o sortare dupa capatul stanga reprezinta si o sortare dupa capatul dreapta. Indexam intervalele dupa aceasta ordine. Al i-lea interval este cel cu al i-lea capat stanga. Deoarece alegand o pozitie k de pe axa Ox acoperim o secventa continua de astfel de intervale, putem construi dinamica:

* @dp[i] = costul minim de a acoperi primele i intervale.@

Parcurgem pozitiile de pe axa Ox de la stanga la dreapta. Presupunem ca stim configuratia de intervale la care suntem la pozitia i. Aceasta va fi o secventa continua de intervale - [l..r], unde l este cel mai din stanga interval iar r este cel mai din dreapta. intervalele [1..l-1] trebuiau acoperite cu pozitii mai mici decat aceasta, nu mai avem cum sa le acoperim de aici. Asadar, este necesar si suficient sa actualizam @dp[k] = min (dp[k], dp[l-1] + v[i])@ pentru oricare k cu l ≤ k ≤ r. Mai jos aveti codul pentru a intelege mai bine:

Parcurgem pozitiile de pe axa Ox de la stanga la dreapta. Presupunem ca stim configuratia de intervale. Presupunem ca suntem la pozitia i si stim configuratia de intervale care trece prin aceasta pozitie. Aceasta va fi o secventa continua de intervale - [l..r], unde l este cel mai din stanga interval iar r este cel mai din dreapta. intervalele [1..l-1] trebuiau acoperite cu pozitii mai mici decat aceasta, nu mai avem cum sa le acoperim de aici. Asadar, este necesar si suficient sa actualizam @dp[k] = min (dp[k], dp[l-1] + v[i])@ pentru oricare k cu l ≤ k ≤ r. Mai jos aveti codul pentru a intelege mai bine:

== code(cpp) |
int get_answer (vector<pair<int,int> > intervals)