Cod sursa(job #1386835)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 13 martie 2015 12:53:03
Problema Subsir 2 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#define INF 1000000000
#define MAXN 5000
int d[MAXN+1], v[MAXN+1], next[MAXN+1];
int main(){
    int n, i, j, p, min;
    FILE *fin, *fout;
    fin=fopen("subsir2.in", "r");
    fout=fopen("subsir2.out", "w");
    fscanf(fin, "%d", &n);
    v[0]=-INF;
    for(i=1; i<=n; i++){
        fscanf(fin, "%d", &v[i]);
    }
    for(i=n; i>=0; i--){
        min=d[i]=INF;
        for(j=i+1; j<=n; j++){
            if((v[j]>=v[i])&&(v[j]<min)){
                min=v[j];
                if((d[i]>d[j]+1)||((d[i]==d[j]+1)&&(v[j]<v[next[i]]))){
                    d[i]=d[j]+1;
                    next[i]=j;
                }
            }
        }
        if(d[i]==INF){
            d[i]=1;
            next[i]=n+1;
        }
    }
    fprintf(fout, "%d\n%d", d[0]-1, next[0]);
    p=next[next[0]];
    while(p!=n+1){
        fprintf(fout, " %d", p);
        p=next[p];
    }
    fprintf(fout, "\n");
    fclose(fin);
    fclose(fout);
    return 0;
}