Cod sursa(job #2250168)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 30 septembrie 2018 12:57:46
Problema Subsir 2 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>

using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int i,j,n,l[5001],tata[5001],v[5001],x,lmin,c,sol[5001],mini,poz;
int main()
{   f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    l[n]=1;
    tata[n]=0;
    for(i=n-1;i>=1;i--){
        mini=1000001;
        tata[i]=0;
        l[i]=1;
        for(j=i+1;j<=n;j++){
            if(v[i]<=v[j]&&v[j]<mini){
                if(l[j]<=l[poz]){
                    l[i]=l[j]+1;
                    tata[i]=j;
                }
            if(mini>v[j]){
                mini=v[j];
                poz=j;
            }
            }

        }
        if(l[i]>lmin){
            lmin=l[i];
            x=i;
        }
        else
            if(l[i]==lmin)
                if(v[i]<v[x])
                    x=i;
    }
    g<<lmin<<'\n';
    c=0;
    while(x!=0){
        sol[++c]=x;
        x=tata[x];
    }
    for(i=1;i<=lmin;i++)
        g<<sol[i]<<' ';
    return 0;
}