Cod sursa(job #2250268)

Utilizator anamariatoaderAna Toader anamariatoader Data 30 septembrie 2018 13:28:33
Problema Subsir 2 Scor 97
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>

using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int n,i,j,v[5001],l[5001],tata[5001],lMin,p,Min,poz,sol[5001],pozmin;
int main(){
    fin>>n;
    int minim=1000001;
    for(i=1;i<=n;i++){
        fin>>v[i];
        l[i]=1;
        if(v[i]<minim){
            minim=v[i];
            pozmin=i;
        }
    }
    l[n]=1; l[n+1]=5001;
    tata[n]=0;
    Min=v[n];
    for(i=n-1;i>0;i--){
        Min=1000001; poz=n+1;
        for(j=i+1;j<=n;j++){
            if(v[i]<=v[j]&&v[j]<Min){
                if(l[j]<=l[poz]){
                    l[i]=l[j]+1;
                    tata[i]=j;
                    poz=j;
                }
                Min=v[j];
            }
        }
    }
    lMin=5001;minim=10000001;
    for(i=1;i<=pozmin;i++)
        if(l[i]<=lMin&&v[i]<minim){
            lMin=l[i];
            minim=v[i];
            p=i;
        }
fout<<l[p]<<'\n';
    while(p>0){
       fout<<p<<' ';
       p=tata[p];
    }
    return 0;
}