*Subproblema 2*

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:
 
* @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 updatam @dp[k] = min (dp[k], dp[l-1] + v[i]) pentru orice l ≤ k ≤ r. Mai jos aveti codul pentru a intelege mai bine:
 
== code(cpp) |
int get_answer (vector<pair<int,int> > intervals)
{
    sort (intervals.begin(), intervals.end());
 
    for (int i = 0; i < intervals.size(); ++i)
    {
        bal[intervals[i].first][0].push_back(i+1);
        bal[intervals[i].second][1].push_back(i+1);
    }
 
    for (int i = 1; i <= intervals.size(); ++i)
        dp[i] = inf;
 
    int not_present = 0;
    int present = 0;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < bal[i][0].size(); ++j)
        {
            present = max (present, bal[i][0][j]);
        }
 
        for (int j = not_present+1; j <= present; ++j)
        {
            dp[j] = min (dp[j], dp[not_present] + v[i]);
        }
 
        for (int j = 0; j < bal[i][1].size(); ++j)
        {
            not_present = max(not_present, bal[i][1][j]);
        }
    }
 
    return dp[intervals.size()];
}
==
 

==include(page="onis-2015/solutii-runda-1/cifrul")==
==include(page="onis-2015/solutii-runda-1/invazia")==