Cod sursa(job #831165)

Utilizator avaspataruAva Spataru avaspataru Data 8 decembrie 2012 11:09:41
Problema Subsir 2 Scor 62
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdio.h>
int i,j,n,v[50001],vc[50001],ppminim,maxim,maximul,elemminim,ci,lung,minimul,pozminim;
int main(){
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    vc[n]=1;
    maximul=1;
    for(i=n-1;i>=1;i--){
        maxim=-1;
        for(j=n;j>i;j--)
            if(vc[j]>maxim&&v[j]>=v[i])
                maxim=vc[j];
        if(maxim!=-1)
            vc[i]=maxim+1;
        else
            vc[i]=1;
        /*if(vc[i]>maximul)
            maximul=vc[i];*/
    }
    minimul=100000001;
    for(i=1;i<=n;i++){
        ci=i;
        lung=vc[i];
        for(j=i-1;j>=1;j--){
            if(v[j]<=v[ci]){
                lung++;
                ci=j;
            }
        }
        if(lung<minimul||(lung==minimul&&v[ci]<pozminim)){
            minimul=lung;
            pozminim=ci;
        }
    }
    printf("%d\n",minimul);
    maximul=minimul-1;
    printf("%d ",ci);

    ppminim=0;
    while(maximul>0){
        //il caut pe maximul
        elemminim=1000001;
        for(i=ppminim+1;i<=n;i++){
            if(vc[i]==maximul&&v[i]<elemminim&&v[i]>=v[ppminim]){
                pozminim=i;
                elemminim=v[i];
            }
        }
        printf("%d ",pozminim);
        ppminim=pozminim;
        maximul--;
    }
    return 0;
}