Cod sursa(job #1463658)

Utilizator EpictetStamatin Cristian Epictet Data 21 iulie 2015 14:07:27
Problema Subsir 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 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] = 1000000000;
        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 < DP[i] && (V[j] < minim || V[j] > minim_nr))
                {
                    DP[i] = DP[j] + 1;
                    Poz[i] = j;
                    minim = min (minim, V[j]);
                }
                else if (DP[j] + 1 == DP[i] && (V[j] < minim || V[j] > minim_nr))
                {
                    Poz[i] = j;
                    minim = V[j];
                }
                minim = min (minim, V[j]);
            }
        }
        if (DP[i] == 1000000000) DP[i] = 1;
    }

    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;
}