Cod sursa(job #931772)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 28 martie 2013 14:46:23
Problema Subsir 2 Scor 63
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>

using namespace std;

const int MAX_N = 5002;

int N, Max, Res;
int D[MAX_N], a[MAX_N], t[MAX_N], v[MAX_N];

int main()
{
    ifstream f("subsir2.in");
    ofstream g("subsir2.out");

    f >> N;
    for(int i = 1; i <= N; ++i)
        f >> v[i];

    D[N] = 1;
    for(int i = N-1; i; --i)
    {
        int Min = 1000005, p = 0;
        D[i] = N+1;
        for(int j = i+1; j <= N; ++j)
            if(v[j] < Min && v[j] >= v[i])
            {
                t[j] = 1;
                if(D[j] < D[i] || (v[j] < v[p] && D[j] == D[i]))
                    Min = v[j], D[i] = D[j], p = j;
            }
        a[i] = p;
        ++D[i];
        if(D[i] > N)
            D[i] = 1;
    }

    int p = 0;
    Res = N+1;
    for(int i = 1; i <= N; ++i)
        if(!t[i] && D[i] < Res)
            Res = D[i], p = i;

    g << Res << '\n';
    while(p)
        g << p << " ", p = a[p];

    f.close();
    g.close();

    return 0;
}