Cod sursa(job #2250245)

Utilizator anamariatoaderAna Toader anamariatoader Data 30 septembrie 2018 13:23:19
Problema Subsir 2 Scor 57
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 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;
    for(i=1;i<=pozmin;i++){
        if(l[i]<lMin){
            lMin=l[i];
            minim=v[i];
            p=i;
        }
        else
            if(l[i]==lMin&&v[i]<minim){
                minim=v[i];
                p=i;
            }
    }
    for(i=1;i<=lMin;i++){
        sol[i]=p;
        p=tata[p];
    }
    fout<<lMin<<'\n';
    for(i=1;i<=lMin;i++)
        fout<<sol[i]<<" ";
    return 0;
}