Cod sursa(job #1714510)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 8 iunie 2016 15:48:20
Problema Subsir 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
# include <fstream>
# define DIM 5010
# define INF 2000000000
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int v[DIM],l[DIM],sol[DIM],t[DIM],a[DIM],b[DIM];
int n,i,j,maxim,minim,poz,k,r,k1,k2,ok;
int main () {
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    l[1]=1;
    for(i=2;i<=n;i++){
        minim=INF;
        maxim=-INF;
        for(j=i-1;j>=1;j--){
            if(v[j]<=v[i]&&v[j]>maxim){
                maxim=v[j];
                if(l[j]+1==minim){
                    r=j;
                    k1=0;
                    k2=0;
                    ok=1;
                    while(r!=0){
                        a[++k1]=v[r];
                        r=t[r];
                    }
                    r=t[i];
                    while(r!=0){
                        b[++k2]=v[r];
                        r=t[r];
                    }
                    for(r=k1;r>=1;r--)
                        if(a[r]>b[r])
                            ok=0;
                    if(ok)
                        t[i]=j;
                }
                if(l[j]+1<minim){
                    minim=l[j]+1;
                    t[i]=j;
                }
            }
        }
        l[i]=minim;
        if(l[i]==INF)
            l[i]=1;
    }
    maxim=-INF;
    minim=INF;
    for(i=n;i>=1;i--){
        if(v[i]>maxim){
            maxim=v[i];
            if(l[i]<minim){
                minim=l[i];
                poz=i;
            }
        }
    }
    fout<<minim<<"\n";
    i=poz;
    while(i!=0){
        sol[++k]=i;
        i=t[i];
    }
    for(i=k;i>=1;i--)
        fout<<sol[i]<<" ";
    fout<<"\n";
    return 0;
}