记录编号	336290	评测结果	AAAAAA
题目名称	[NOIP 2000]方格取数	最终得分	100
用户昵称	Mealy	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2016-11-03 07:40:31	内存使用	0.46 MiB

#include <cstdio>


using namespace std;

const int nmax=18;


int n;
int s[nmax][nmax]={0};
int tmpx=0,tmpy=0,tmpval=0;
int tmp;


int f[nmax][nmax][nmax][nmax]={0};


void PreDo()
{
	scanf("%d",&n);
	while(1)
	{
		scanf("%d%d%d",&tmpx,&tmpy,&tmpval);
		if(tmpx==0&&tmpy==0&&tmpval==0)
		{
			return;
		}
		s[tmpx][tmpy]=tmpval;
	}
}


int Max(int a,int b,int c,int d)
{
	int t[4];
	t[0]=a;
	t[1]=b;
	t[2]=c;
	t[3]=d;
	int tmpmax=t[0];
	for(int i=0;i<4;i++)
	{
		if(t[i]>tmpmax)
		{
			tmpmax=t[i];
		}
	}
	return tmpmax;
}


void DP()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				for(int l=1;l<=n;l++)
				{
					tmp=Max(f[i-1][j][k-1][l],f[i][j-1][k-1][l],f[i][j-1][k][l-1],f[i-1][j][k][l-1]);
					f[i][j][k][l]=tmp+s[i][j];
					if(i!=k||j!=l)
					{
						f[i][j][k][l]+=s[k][l];
					}
				}
			}
		}
	}
	printf("%d\n",f[n][n][n][n]);
}

int main()
{
	freopen("fgqs.in","r",stdin);
	freopen("fgqs.out","w",stdout);
	PreDo();
	DP();
	return 0;
}