记录编号	42508	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺六]数列游戏	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2012-09-25 22:25:18	内存使用	9.53 MiB

#include <cstdio>
using namespace std;

int a[1100],right[1100],rightnum[1100][1100],f[1100][1100];

int main(void)
{
	freopen("seqgame.in","r",stdin);
	freopen("seqgame.out","w",stdout);
	int i,j,n,temp,f2;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		right[i]=i-a[i];
		for (j=0;j<=n;j++)
			rightnum[i][j]=rightnum[i-1][j];
		if (right[i]<0)
		{
			right[i]=-1;
		}
		else
		{
			rightnum[i][right[i]]++;
		}
	}
	for (i=1;i<=n;i++)
	{/*
		f[i][0]=rightnum[i][0];
		for (j=1;j<i;j++)
		{
			if (right[i]==j)
				temp=1;
			else
				temp=0;
			f[i][j]=f[i-1][j]+temp;
			if (f[i][j]<f[i-1][j])
				f[i][j]=f[i-1][j];
		}*/                                    /*  No 1  */
		f[i][0]=rightnum[i][0];
		for (j=1;j<i;j++)
		{
			/*do not get it*/
			if (right[i]==j)
				temp=1;
			else
				temp=0;
			f[i][j]=f[i-1][j]+temp;
			if (f[i][j]<f[i-1][j-1])
				f[i][j]=f[i-1][j-1];
			/*do not get it*/
//			if (i==n)
//				continue;
			/*get it!*//*
			if (right[i+1]==j+1)
				temp=1;
			else
				temp=0;
			f2=f[i-1][j-1]+temp;
			if (f[i][j]<f2)
				f[i][j]=f2;
			*//*get it!*/                     /*  No 2  */
		}
	}
	temp=0;
	for (i=1;i<n;i++)
		if (temp<f[n][i])
			temp=f[n][i];
	printf("%d\n",temp);
	return(0);
}