Cod sursa(job #906810)

Utilizator RaduDoStochitoiu Radu RaduDo Data 7 martie 2013 10:47:46
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<iostream>
#include<cstdio>
#define INF 0x3f3f3f3f
#define maxn 5005
using namespace std;
int x[maxn],L[maxn],poz[maxn],n,i,j,Min,ante,val,Minim,st;
bool check[maxn];
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>=1 ; --i)
    {
        L[i]=1;
        poz[i]=i;
        check[i]=true;
        Minim=INF;
        Min=INF;
        for(j=i+1; j<=n; ++j)
        {
            if(x[i]<=x[j])
            {
                if(L[j]<Minim && x[j]<Min)
                {
                    Minim=L[j];
                    poz[i]=j;
                    L[i]=L[j]+1;
                }
                else
                    if(L[j]==Minim && x[j]<Min && x[j]<=x[poz[i]])
                        poz[i]=j;
                if(x[j]<Min)
                    Min=x[j];
                check[j]=false;
            }
        }
    }

    Minim=INF;
    for(i=1; i<=n; ++i)
        if(check[i]==true)
        {
            if(L[i]<Minim)
            {
                Minim=L[i];
                st=i;
            }
            else
                if(L[i]==Minim && x[st]>x[i])
                    st=i;

        }
    printf("%d\n%d ",L[st],st);
    while(poz[st]!=st)
    {
        printf("%d ",poz[st]);
        st=poz[st];
    }
    return 0;
}