Cod sursa(job #907353)

Utilizator profcntvProfCNTV profcntv Data 7 martie 2013 21:20:06
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
# include<cstdio>
# include<climits>
# define maxn 5010
using namespace std;
int x[maxn],L[maxn],P[maxn],i,j,n,Max,Min,poz,p,k,val,start;
int main()
{
    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=n; i>0; --i)
    {
        Min = val = INT_MAX;
        L[i] = 1; P[i] = -1;
        for(j=i+1; j<=n; ++j)
            if (x[i] <= x[j])
            {
                if(Min > L[j] && x[j] < val)
                {
                    Min = L[j];
                    P[i] = j;
                    L[i] = 1 + L[j];
                }
                else if(L[j]==Min && x[j]<val && x[j]<=x[P[i]])
                        P[i]=j;
                if(x[j]<val) val = x[j];
            }
    }
    Max = 0;
    for(i=1; i<=n; ++i)
        if(L[i]>Max)
            {
                Max = L[i];
                start = i;
            }
            else
                if(L[i]==Max && x[start]>x[i])
                    start=i;

    printf("%d\n",L[start]);
    while(start!=-1)
        printf("%d ",start), start=P[start];
    return 0;
}