Pagini recente » Cod sursa (job #1319191) | Cod sursa (job #2988649) | Cod sursa (job #702811) | Cod sursa (job #3221235) | Cod sursa (job #992701)
Cod sursa(job #992701)
#include<stdio.h>
#include<cstring>
#include<algorithm>
#define maxn 5005
#define inf 0x3f3f3f3f
using namespace std;
int n,s,len=inf,pos;
int a[maxn];
int best[maxn],p[maxn],dw[maxn];
void read()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
}
void solve()
{
int i,j,minn,pc;
for(i=1;i<=n;i++) dw[i]=-inf;
best[n]=1; a[0]=inf;
for(i=n-1;i;i--)
{
minn=inf; pc=0;
for(j=i+1;j<=n;j++) if(a[j]>=a[i])
{
if(dw[j]<a[i])
if(minn>best[j] || (best[j]==minn && a[j]<a[pc]))
minn=best[j],pc=j;
dw[j]=max(dw[j],a[i]);
}
best[i]=best[pc]+1; p[i]=pc;
}
for(i=1;i<=n;i++)
if(dw[i]==-inf)
if(len>best[i] || (len==best[i] && a[pos]>a[i]))
{
pos=i;
len=best[i];
}
printf("%d\n",len);
for(i=pos;i;i=p[i]) printf("%d ",i);
}
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
read();
solve();
fclose(stdin);
fclose(stdout);
return 0;
}