记录编号	106026	评测结果	AAAAAA
题目名称	[NOIP 2000]方格取数	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2014-06-13 07:27:53	内存使用	0.30 MiB

#include <cstdio>

int f[21][11][11];
/*
f[k][i1][i2]两个纸条都走了K步
第1个纸条横坐标为i1,第2个纸条横坐标为i2的最优值
这样就相当于一个区域动规了 区域 ([0][0],[i1][i2])分k步走完
每个区域又上一个区域推出
*/  
int c[12][12];

int main()
{
	freopen("fgqs.in" ,"r",stdin );
	freopen("fgqs.out","w",stdout);
	int n,x,y,v;
	scanf("%d",&n);
	while (true)
	{
		scanf("%d%d%d",&x,&y,&v);
		if (x==0&&y==0&&v==0) break;
		else c[x][y]=v;
	}
	for (int k = 1 ; k <= n*2 ; k ++ )//最多n*2个不同步数（包括(0,0)(n,n)）； 
	{
		for (int i1 = 1 ; i1 <= n ; i1 ++ )
		{
			if (i1 > k) break ;
			for (int i2 = 1 ; i2 <= n ; i2 ++ )
			{
				if (i2 > k) break ; 
				f[k][i1][i2] = f[k-1][i1][i2];
				if (f[k-1][i1][i2-1] > f[k][i1][i2])f[k][i1][i2] = f[k-1][i1][i2-1];
				if (f[k-1][i1-1][i2] > f[k][i1][i2])f[k][i1][i2] = f[k-1][i1-1][i2];
				if (f[k-1][i1-1][i2-1] > f[k][i1][i2])f[k][i1][i2] = f[k-1][i1-1][i2-1];
				f[k][i1][i2] += c[i1][k-i1] ;
				if (i1 != i2) f[k][i1][i2] += c[i2][k-i2] ;
			}
		}
	}
	printf("%d\n",f[2*n][n][n]);
	return 0;
}