Cod sursa(job #1463662)

Utilizator EpictetStamatin Cristian Epictet Data 21 iulie 2015 14:13:46
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>

using namespace std;

ifstream fin ("subsir2.in");
ofstream fout ("subsir2.out");

int N, V[5010], DP[5010], Poz[5010];

int main()
{
    fin >> N;
    for (int i = 1; i <= N; i++) fin >> V[i];

    V[0] = -1000000000;
    int maxim = 0, start, minim, minim_nr;
    for (int i = N; i >= 0; i--)
    {
        DP[i] = 1000000000;
        Poz[i] = i;
        minim = 1000000000;
        for (int j = i + 1; j <= N; j++)
        {
            if (V[i] <= V[j] && V[j] < minim)
            {
                minim = V[j];
                if (DP[j] + 1 < DP[i])
                {
                    DP[i] = DP[j] + 1;
                    Poz[i] = j;
                }
                else if (DP[j] + 1 == DP[i] && V[j] < V[Poz[i]])
                {
                    Poz[i] = j;
                    minim = V[j];
                }
            }
        }
        if (DP[i] == 1000000000) DP[i] = 1;
    }

    minim = 1000000000;

    fout << DP[0] - 1 << '\n';
    while (Poz[start] != start)
    {
        start = Poz[start];
        fout << start << ' ';
    }

    return 0;
}