Cod sursa(job #340430)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 14 august 2009 17:38:20
Problema Subsir 2 Scor 61
Compilator c Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>
#define NMAX 5005
#define Inf 0x3f3f3f3f
int N,x[NMAX],din[NMAX],t[NMAX];
int Sol[NMAX],a[NMAX],b[NMAX];
int main()
{
    int i,j,most;
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    scanf("%d",&N);
    for (i=1;i<=N;++i) scanf("%d",&x[i]);
    for (i=1;i<=N;++i)
    {
        most=-Inf;
        din[i]=Inf;
        for (j=i-1;j;--j)
          if (x[j] < x[i] && x[j] >= most)
          {
             most=x[j];
             if (din[j]+1 < din[i]) 
               {
                din[i]=din[j]+1;
                t[i]=j;
               }
             else 
             if (din[j]+1 == din[i] && x[t[i]] > x[j]) t[i]=j;
          }
        if (most == -Inf) din[i]=1;
    }
    int lmin=Inf;
    most=-Inf;
    for (i=N;i;i--)
        if (x[i] >= most)
        {
            if (lmin > din[i]) lmin=din[i];
            most=x[i];
        }
    printf("%d\n",lmin);
    for (i=1;i<=lmin;++i) Sol[i]=Inf;
    most=-Inf;
    for (i=N;i;i--)
        if (x[i] >= most) 
        {
           most=x[i];
           if (lmin == din[i])
           {
            int k=lmin;
            for (j=i;j>0;j=t[j]) a[k--]=x[j];
            for (j=1;Sol[j] == a[j] && j<=lmin;++j);
            if (j==lmin+1) continue;
            if (Sol[j] > a[j])
             {
                k=lmin;
                for (j=i;j;j=t[j]) b[k--]=j; 
                for (j=1;j<=lmin;++j) Sol[j]=a[j];
             }
           }   
        }
    for (i=1;i<=lmin;++i) printf("%d ",b[i]);
    return 0;
}