Cod sursa(job #1463578)

Utilizator EpictetStamatin Cristian Epictet Data 21 iulie 2015 11:59:10
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 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;
    for (int i = N; i >= 1; i--)
    {
        DP[i] = 1;
        Poz[i] = -1;
        int minim = 1000000000;
        for (int j = i + 1; j <= N; j++)
        {
            if (V[i] <= V[j])
            {
                if (DP[i] < DP[j] + 1)
                {
                    DP[i] = DP[j] + 1;
                    Poz[i] = j;
                    minim = min (minim, V[j]);
                }
                else if (DP[i] == DP[j] + 1 && V[j] < minim)
                {
                    Poz[i] = j;
                    minim = V[j];
                }
            }
        }
        if (DP[i] > maxim) maxim = DP[i], start = i;
        else if (DP[i] == maxim && V[i] < V[start]) start = i;
    }

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

    return 0;
}