Cod sursa(job #1599987)

Utilizator Master011Dragos Martac Master011 Data 14 februarie 2016 16:21:40
Problema Subsir 2 Scor 59
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<cstdio>
using namespace std;

const int nMax = 5000 + 1, INF = 1000001;
int v[nMax], d[nMax], urm[nMax];

int main (){
    FILE *in = fopen("subsir2.in","r");
    FILE *out = fopen("subsir2.out","w");

    int n, minNr;
    fscanf(in,"%d", &n);
    for(int i = 1 ; i <= n ; ++i) fscanf(in,"%d", v + i);

    v[0] = -INF;

    for(int i = n; i >= 0 ; --i){
        d[i] = minNr = INF;
        for(int j = i + 1 ; j <= n ; ++j){
            if(v[j] > v[i] && v[j] < minNr){
                minNr = v[j];
                if((d[j] + 1 < d[i]) || (d[j] + 1 == d[i] && v[urm[i]] > v[j])){
                    d[i] = d[j] + 1;
                    urm[i] = j;
                }
            }
        }
        if(d[i] == INF){
            d[i] = 1;
            urm[i] = n + 1;
        }
    }

    fprintf(out,"%d\n", d[0] - 1);
    for(int i = urm[0] ; i <= n ; i = urm[i]){
        fprintf(out,"%d ", i);
    }
    fprintf(out,"\n");
    return 0;
}