Cod sursa(job #1731387)

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