Cod sursa(job #17440)
Utilizator | Data | 15 februarie 2007 21:24:56 | |
---|---|---|---|
Problema | Subsir 2 | Scor | 64 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.43 kb |
#include<stdio.h>
const int maxn = 10001;
const int inf = 100000000;
int a[maxn];
int i;
int n;
int min;
int la[maxn];
int le[maxn];
int poz;
int j;
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]+=1000001;
}
for(j=n;j>=1;j--)
{
le[j]=inf;
la[j]=0;
min=inf;
for(i=j+1;i<=n;i++)
{
if (a[i]<min&&a[i]>=a[j]) min=a[i];
if (min==a[i]&&a[i]>=a[j]&&(le[i]+1<le[j]||(le[i]+1==le[j]&&a[la[j]]>a[i])))
{
le[j]=le[i]+1;
la[j]=i;
}
}
if (le[j]==inf) le[j]=1;
}
min=inf;
int min1=inf;
poz=inf;
for(i=1;i<=n;i++)
{
if (a[i]<min1) min1=a[i];
if (a[i]==min1&&(le[i]<min||(a[poz]>a[i]&&le[i]==min)))
{
min=le[i];
poz=i;
}
}
printf("%d\n",le[poz]);
while(poz)
{
printf("%d ",poz);
poz=la[poz];
}
return 0;
}