Cod sursa(job #1453911)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 24 iunie 2015 23:53:31
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<cstdio>
using namespace std;
int lmin[5001],v[5001],urm[5001],sol[5001];
int main(){
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    int n,maxi,i,j,mini,poz,minim;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(i=n;i>=1;i--){
        mini=10000;
        minim=2000000000;
        for(j=i+1;j<=n;j++)
            if(v[j]>=v[i])
                if(v[j]<minim){
                    minim=v[j];
                    if(lmin[j]<mini){
                        mini=lmin[j];
                        urm[i]=j;
                    }
                    else
                        if(lmin[j]==mini&&v[j]<v[urm[i]])
                            urm[i]=j;
                }
        if(mini!=10000)
            lmin[i]=mini+1;
        else{
            lmin[i]=1;
            urm[i]=i;
        }
    }
    minim=2000000000;
    mini=100000;
    for(i=1;i<=n;i++)
        if(v[i]<minim){
            minim=v[i];
            if(lmin[i]<mini){
                mini=lmin[i];
                poz=i;
            }
            else
                if(lmin[i]==mini&&v[i]<v[poz])
                    poz=i;
        }
    printf("%d\n",mini);
    for(i=1;i<=mini;i++){
        printf("%d ",poz);
        poz=urm[poz];
    }
    return 0;
}