记录编号	411930	评测结果	AAAAAA
题目名称	[NOIP 2000]方格取数	最终得分	100
用户昵称	FFF团	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2017-06-07 10:19:35	内存使用	0.37 MiB

#include<bits/stdc++.h>
using namespace std;
int s[11][11];
int n,a,b,c;
int dp[11][11][11][11];
int dfs(int a,int b,int c,int d){
	if(a==n&&b==n&&c==n&&d==n)return dp[n][n][n][n]=s[n][n];
	if(dp[a][b][c][d])return dp[a][b][c][d];
	int ss=0;
	if(s[a][b])ss+=s[a][b];
	if(s[c][d])ss+=s[c][d];
	if(a==c&&b==d)ss-=s[a][b];
	int t=0;
	if(a+1<=n){
		if(c+1<=n)t=max(t,dfs(a+1,b,c+1,d));
		if(d+1<=n)t=max(t,dfs(a+1,b,c,d+1));
	}
	if(b+1<=n){
		if(c+1<=n)t=max(t,dfs(a,b+1,c+1,d));
		if(d+1<=n)t=max(t,dfs(a,b+1,c,d+1));
	}
	ss+=t;
	return dp[a][b][c][d]=ss;
}
int main(){
	freopen("fgqs.in","r",stdin);
	freopen("fgqs.out","w",stdout);
	scanf("%d%d%d%d",&n,&a,&b,&c);
	while(a&&b&&c){
		s[a][b]=c;
		scanf("%d%d%d",&a,&b,&c);
	}
	printf("%d",dfs(1,1,1,1));
	return 0;
}