Cod sursa(job #66149)

Utilizator devilkindSavin Tiberiu devilkind Data 16 iunie 2007 11:30:51
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <stdio.h>
#define NMAX 5005
long int a[NMAX],v[NMAX],s[NMAX],sol[NMAX],TT[NMAX];
long int n,i,j,k;

void citire()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%ld",&n);
for (i=1;i<=n;i++)
        scanf("%ld",&a[i]);
}

void solve()
{
long int max;
max=a[n];s[n]=1;
long int st[NMAX];
for (i=n-1;i>=1;i--)
        if (a[i]>max) {s[i]=1;max=a[i];}
                else s[i]=0;
long int min;
min=a[1];
for (i=2;i<=n;i++)
        if (a[i]<min) {st[i]=1;min=a[i];} else st[i]=0;
v[1]=1;TT[i]=0;
for (i=2;i<=n;i++)
        {
        max=0;
        v[i]=5005;
        TT[i]=0;
        if (st[i]==1) {TT[i]=0;v[i]=1;}
        for (j=i-1;j>=1;j--)
                {                
                if (a[j]>a[i]) continue;
                if (a[j]<max) continue;                
                if ((a[j]>=max)&&(v[j]<v[i]-1)) {v[i]=v[j]+1;TT[i]=j;max=a[j];continue;}
                if ((a[j]==max)&&(v[j]==v[i]-1)&&(a[j]<a[TT[i]])) TT[i]=j;
                if (max<a[j]) max=a[j];
                }
        }
max=0;
long int x;
long int sol2[NMAX],ok=0;;
for (i=1;i<=n;i++)
      if ((s[i])&&(v[i]>=max)) {max=v[i];x=i;
                              k=0;
                              for (;x>0;x=TT[x])
                                sol2[++k]=x;
                              if (ok==0) {for (k=1;k<=max;k++) sol[k]=sol2[k];ok=1;continue;}
                              for (k=max;(sol[k]==sol2[k])&&(k>0);k--);
                              if (k&&(a[sol2[k]]<a[sol[k]])) for (k=1;k<=max;k++) sol[k]=sol2[k];
                              }
k=0;
printf("%ld\n",max);
for (i=max;i>=1;i--)
        printf("%ld ",sol[i]);
}

int main()
{
citire();
solve();
return 0;
}