Cod sursa(job #1463653)

Utilizator EpictetStamatin Cristian Epictet Data 21 iulie 2015 14:00:18
Problema Subsir 2 Scor 69
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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];

    int maxim = 0, start, minim, minim_nr;

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

    minim = 1000000000;
    for (int i = 1; i <= N; i++)
    {
        if (minim > V[i])
        {
            minim = V[i];
            start = i;
        }
    }
    fout << DP[start] << '\n';
    while (Poz[start] != start)
    {
        fout << start << ' ';
        start = Poz[start];
    }
    fout << start << '\n';

    return 0;
}