Cod sursa(job #204183)

Utilizator savimSerban Andrei Stan savim Data 22 august 2008 13:27:55
Problema Subsir 2 Scor 7
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 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) min=v[j];
        }
    }
    
    min=val_max;p=val_max;
    for (i=1; i<=n; i++)
        if (v[i]<min && v[i]<p)
        {
           p=v[i];k=i;
           min=v[i];
        }
    
    printf("%d\n",c[k]);
    while (k>0)
    {
          printf("%d ",k);
          k=vine[k];
    }
    
    return 0;    
}