Pagini recente » Cod sursa (job #2342904) | Cod sursa (job #2928781) | Cod sursa (job #3231632) | Cod sursa (job #2563523) | Cod sursa (job #19173)
Cod sursa(job #19173)
#include <cstdio>
#include <string>
#define maxn 5001
int main()
{
int n, x[maxn], dp[maxn], pi[maxn];
freopen("subsir2.in", "r", stdin);
scanf("%d\n", &n);
int i, j;
for(i=1;i<=n;i++) scanf("%d ", x+i);
memset(dp, 0x3f3f3f3f, sizeof(dp));
memset(pi, -1, sizeof(pi));
dp[n]=1;
int ok, min;
for(i=n-1;i>=1;--i)
{
dp[i]=0x3f3f3f3f;
ok=0;
min=0x3f3f3f3f;
for(j=i+1;j<=n;j++)
{
if(x[i]<=x[j] && dp[j]+1<dp[i] && x[j]<=min)
{
dp[i]=dp[j]+1;
pi[i]=j;
ok=1;
}
if(x[i]<=x[j] && dp[j]+1==dp[i] && x[j]<=min)
if(x[pi[i]]>x[j])
{
dp[i]=dp[j]+1;
pi[i]=j;
ok=1;
}
if(x[j]<min && x[j]>=x[i]) min=x[j];
//printf("%d\n", min);
}
if(!ok) dp[i]=1, pi[i]=i;
}
int max=0, poz=-1;
//for(i=1;i<=n;i++) printf("%d ", x[i]);
//printf("\n");
//for(i=1;i<=n;i++) printf("%d ", pi[i]);
for(i=1;i<=n;i++) if(dp[i]>max && dp[i]!=0x3f3f3f3f) max=dp[i], poz=i;
freopen("subsir2.out", "w", stdout);
printf("%d\n", max);
for(i=poz;i!=-1; i=pi[i]) printf("%d ", i);
printf("\n");
return 0;
}