Cod sursa(job #1142155)

Utilizator andreiagAndrei Galusca andreiag Data 13 martie 2014 16:00:30
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>

using namespace std;
const int Nmax = 5005;
const int INF = 10000000;

int A[Nmax];
int D[Nmax];
int Next[Nmax];

int N;

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

    f >> N;

    for (int i = 0; i < N; i++) {
        f >> A[i];
        D[i] = 1;
        Next[i] = -1;
    }

    int premin = INF;
    for (int n = N-1; n >-1; n--) {
        premin = INF;
        for (int i = n+1; i < N; i++) {
            if (A[i] >= A[n] && A[i] < premin) {
                premin = A[i];
                if (D[n] == 1 || D[n] >= D[i] + 1) {
                    D[n] = D[i] + 1;
                    if (A[Next[n]] > A[i] || Next[n] == -1)
                        Next[n] = i;
                }
            }
        }
    }

    int best = INF;
    int start = -1;
    premin = INF;
    for (int i = 0; i < N; i++) {
        if (A[i] < premin) {
            premin = A[i];
            if (D[i] <= best) {
                best = D[i];
                if (start == -1 || A[i] < A[start])
                    start = i;
            }
        }
    }
/*
    for (int i = 0; i < N; i++)
        g << D[i] << (i==N-1?'\n':'_');
    for (int i = 0; i < N; i++)
        g << Next[i] << (i==N-1?'\n':'_');
*/

    g << best << '\n';
    while (start > -1) {
        g << start + 1 << ' ';
        start = Next[start];
    }
    g << '\n';

    return 0;
}