Cod sursa(job #1269105)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 21 noiembrie 2014 21:21:04
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>

using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int a[5002],mini,l[5002],n,j,i,d[5002],lg,amin,poz,t[5002];
int main(){
    fin>>n;
    mini=lg=10000001;
    for(i=1;i<=n;i++){
        fin>>a[i];
        if(mini>a[i]) mini=a[i],d[i]=1;
    }
    for(i=n;i>=1;i--){
        l[i]=10000001;mini=10000001;
        for(j=i+1;j<=n;j++){
            if(a[j]>=a[i] && a[j]<mini){
                mini=a[j];
                if(l[i]>l[j]+1)
                    l[i]=l[j]+1,t[i]=j;
                else
                    if(l[i]==l[j]+1 && a[j]<a[t[i]])
                        t[i]=j;
            }

        }
        if(t[i]==0)
            l[i]=1;
        if(d[i]!=0 && l[i]<lg || l[i]==lg && a[i]<amin){
            lg=l[i];
            amin=a[i];
            poz=i;
        }
    }
    fout<<l[poz]<<"\n";
    while(poz!=0)
    {
        fout<<poz<<" ";
        poz=t[poz];
    }
    return 0;
}