Cod sursa(job #2250217)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 30 septembrie 2018 13:13:58
Problema Subsir 2 Scor 57
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 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,pozm,minim;
int main()
{   f>>n;
    minim=1000001;
    for(i=1;i<=n;i++){
        f>>v[i];

        if(minim>v[i])
            minim=v[i],pozm=i;
    }
    l[n]=1;
    tata[n]=0;
    l[n+1]=n+1;
    for(i=n-1;i>=1;i--){
        mini=1000001;
        tata[i]=0;
        l[i]=1;poz=n+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;
                    poz=j;
                }
                mini=v[j];
                 }
            }
        }
        lmin=n+1;
    for(i=1;i<=pozm;i++)
    if(lmin>l[i]){
        lmin=l[i];
        x=i;
    }
    else
        if(lmin==l[i]&&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;
}