Cod sursa(job #1731429)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 18 iulie 2016 22:37:34
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#define lim 5005
#define inf 2000000000
int v[lim],lg[lim],next[lim];
int main(){
    FILE *fin,*fout;
    fin=fopen("subsir2.in","r");
    fout=fopen("subsir2.out","w");
    int i,j,n,lgmin,poz,valmin;
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(fin,"%d",&v[i]);
    v[0]=-inf;
    for(i=n;i>=0;i--){
        valmin=inf;
        lgmin=inf;
        poz=0;
        for(j=i+1;j<=n;j++)
            if(v[i]<=v[j]&&v[j]<valmin){
                valmin=v[j];
                if(lg[j]<=lgmin){
                    lgmin=lg[j];
                    poz=j;
                }
            }
        if(lgmin==inf)
            lgmin=0;
        next[i]=poz;
        lg[i]=lgmin+1;
    }
    fprintf(fout,"%d\n",lg[0]-1);
    poz=next[0];
    for(i=1;i<lg[0];i++){
        fprintf(fout,"%d ",poz);
        poz=next[poz];
    }
    fclose(fin);
    fclose(fout);
    return 0;
}