Cod sursa(job #1714512)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 8 iunie 2016 15:58:40
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
# include <fstream>
# define DIM 5010
# define INF 2000000000
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int v[DIM],l[DIM],t[DIM],n,i,j,minim1,minim2,poz,k;
int main () {
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    for(i=n;i>=1;i--){
        minim1=INF;
        minim2=INF;
        for(j=i+1;j<=n;j++){
            if(v[j]>=v[i]&&v[j]<minim2){
                minim2=v[j];
                if(l[j]+1==minim1&&v[j]<v[t[i]])
                    t[i]=j;
                if(l[j]+1<minim1){
                    minim1=l[j]+1;
                    t[i]=j;
                }
            }
        }
        l[i]=minim1;
        if(l[i]==INF)
            l[i]=1;
    }
    minim2=INF;
    minim1=INF;
    for(i=1;i<=n;i++){
        if(v[i]<minim2){
            minim2=v[i];
            if(l[i]==minim1&&v[i]<v[poz])
                poz=i;
            if(l[i]<minim1){
                minim1=l[i];
                poz=i;
            }
        }
    }
    fout<<minim1<<"\n";
    i=poz;
    while(i!=0){
        fout<<i<<" ";
        i=t[i];
    }
    fout<<"\n";
    return 0;
}