Cod sursa(job #206016)

Utilizator savimSerban Andrei Stan savim Data 4 septembrie 2008 10:31:20
Problema Subsir 2 Scor 97
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>

#define maxl 5010
#define val_max 2000000

int i,j,k,n,min,ok,p;
int v[maxl],c[maxl],vine[maxl];

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]);
    
    c[n]=1;vine[n]=-1;
    for (i=n-1; i>=1; i--)
    {
        min=val_max;c[i]=1;vine[i]=-1;
        for (j=i+1; j<=n; j++)
        {
            if (v[j]>=v[i] && min>v[j] &&
                (c[j]+1<c[i] || c[i]==1 || (c[j]+1==c[i] && v[vine[i]]>v[j]))
               )
            {
               c[i]=c[j]+1;
               vine[i]=j;
            }
            if (v[j]<min && v[j]>=v[i]) min=v[j];
        }
    }
    
    min=val_max;p=val_max;
    for (i=1; i<=n; i++)
        if (v[i]<p && c[i]<=min)
        {
           p=v[i];k=i;
           min=c[i];
        }
    
    printf("%d\n",c[k]);
    while (k>0)
    {
          printf("%d ",k);
          k=vine[k];
    }
    
    return 0;    
}