Cod sursa(job #1731375)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 18 iulie 2016 19:40:43
Problema Subsir 2 Scor 59
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 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]);
    for(i=n;i>=1;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&&v[j]<v[poz])
                    poz=j;
                if(lg[j]<lgmin){
                    lgmin=lg[j];
                    poz=j;
                }
            }
        if(lgmin==inf)
            lgmin=0;
        next[i]=poz;
        lg[i]=lgmin+1;
    }
    valmin=inf;
    lgmin=inf;
    for(i=1;i<=n;i++)
        if(v[i]<=valmin){
            valmin=v[i];
            if(lg[i]==lgmin&&v[i]<v[poz])
                poz=i;
            if(lg[i]<lgmin){
                lgmin=lg[i];
                poz=i;
            }
        }
    fprintf(fout,"%d\n",lgmin);
    for(i=poz;i!=0;i=next[i])
        fprintf(fout,"%d ",i);
    fclose(fin);
    fclose(fout);
    return 0;
}