Cod sursa(job #907330)

Utilizator profcntvProfCNTV profcntv Data 7 martie 2013 20:55:12
Problema Subsir 2 Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 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 = INT_MAX; poz=n+1;
        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];
                    poz = j; P[i] = j;
                    val = x[j];
                }
                else if (Min==L[j] && x[j]<=x[poz]) poz=j;
            }
        if (poz <= n) L[i]= 1 + Min, P[i]=poz;
        if(L[i] >= Max) Max = L[i], start = i;
    }

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