Cod sursa(job #19172)

Utilizator gigi_becaliGigi Becali gigi_becali Data 18 februarie 2007 20:44:59
Problema Subsir 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#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;
}