Cod sursa(job #1562585)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 5 ianuarie 2016 12:24:15
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>

#define NMAX 5007
#define INF 1 << 25

using namespace std;

ifstream in("subsir2.in");
ofstream out("subsir2.out");

int Dp[NMAX + 1], a[NMAX + 1], Last[NMAX + 1];
int n, Min, Nr;

int main(void){
    in >> n;
    for (int i = 1; i <= n; ++i)
        in >> a[i];
    a[0] = -INF;
    for (int i = n; i >= 0; --i){
        Min = Dp[i] = INF;
        for (int j = i + 1; j <= n; ++j){
            if ((a[j] < Min) && (a[i] <= a[j])){
                Min = a[j];
                Nr = Dp[j] + 1;
                if ((Dp[i] == Nr) && (a[j] < a[Last[i]]))
                    Last[i] = j;
                if (Nr < Dp[i]){
                    Dp[i] = Nr;
                    Last[i] = j;
                }
            }
        }
        if (Dp[i] == INF){
            Dp[i] = 1;
            Last[i] = i;
        }
    }
    out << Dp[0] - 1 << "\n";
    int k = 0;
    while(k != Last[k]){
        out << Last[k] << " ";
        k = Last[k];
    }
    return 0;
}