Cod sursa(job #200373)

Utilizator CezarMocanCezar Mocan CezarMocan Data 23 iulie 2008 16:08:26
Problema Subsir 2 Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <cstdio>
#include <algorithm>

using namespace std;

long n,v[5010],x[5010],i,j,mx,ant,p[5010],p1[5010],rez,rec[5010],fin[5010],nr,t;

int main(){
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)  
    scanf("%d",&v[i]);
v[0]=2000000000;
x[n]=1;
p[n]=n;
p1[n]=n;
for (i=n-1;i>=1;i--)
    {
    x[i]=1000000000;
    ant=1000000000;
    p[i]=i;
    p1[i]=i;
    for (j=i+1;j<=n;j++)
        if (v[j]>v[i]&&v[j]<ant)
            {
            ant=v[j];
            if (x[i]==(x[j]+1))
                {
                p1[j]=i;
                if (v[j]<v[p[i]])
                    p[i]=j;    
                }
            if (x[i]>x[j]+1)
                {
                x[i]=x[j]+1;   
                p[i]=j; 
                p1[j]=i;
                }
            }        
    if (x[i]==1000000000)
        x[i]=1;
    }
rez=1000000000;
for (i=1;i<=n;i++)
    if (x[i]<rez&&p1[i]==i)
        rez=x[i];
printf("%d\n",rez);
/*for (i=1;i<=n;i++)
    printf("%d ",x[i]);
printf("\n");
for (i=1;i<=n;i++)
    printf("%d ",p[i]);
printf("\n");*/

for (i=1;i<=n;i++)
    {
    if ((x[i]==rez)&&(p1[i]==i))
        {
        nr=1;
        t=i;
        while (t!=p[t])
            {
            rec[nr]=t;
            t=p[t];
            nr++;    
            }
        rec[nr]=t;
        }
    t=1;
    while ((v[rec[t]]==v[fin[t]])&&(t<=rez))
        t++;
    if (v[rec[t]]<v[fin[t]])
        {
        for (t=1;t<=rez;t++)
            fin[t]=rec[t];    
        }
    }
for (i=1;i<=rez;i++)
    printf("%d ",fin[i]);
printf("\n");
return 0;
}