Cod sursa(job #1714334)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 7 iunie 2016 22:42:06
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
# include <fstream>
# define DIM 5010
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int v[DIM],l[DIM],sol[DIM],t[DIM],n,i,j,maxim,minim,poz,k;
int main () {
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    for(i=1;i<=n;i++){
        maxim=0;
        minim=1000000000;
        for(j=i-1;j>=1;j--){
            if(v[i]>=v[j]&&v[j]>maxim&&l[j]+1<minim){
                minim=l[j]+1;
                t[i]=j;
                maxim=v[j];
            }
        }
        if(minim==1000000000)
            l[i]=1;
        else
            l[i]=minim;
    }
    maxim=v[i];
    minim=1000000000;
    for(i=n;i>=1;i--){
        if(v[i]>maxim&&l[i]<minim){
            maxim=v[i];
            minim=l[i];
            poz=i;
        }
    }
    fout<<minim<<"\n";
    i=poz;
    while(i!=0){
        sol[++k]=i;
        i=t[i];
    }
    for(i=k;i>=1;i--)
        fout<<sol[i]<<" ";
    fout<<"\n";
    return 0;
}