记录编号	250804	评测结果	AAWAAA
题目名称	[NOIP 2000]方格取数	最终得分	83
用户昵称	GaoErFu	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-15 22:35:01	内存使用	0.00 MiB

#include<stdio.h>
#include<string.h>
int a[15][15]={0},f[15][15]={0},q[15][15][110][2]={0};
int cc()
{
	freopen("fgqs.in","r",stdin);
    freopen("fgqs.out","w",stdout);
	int N,i,j,k,l=0,x,y,z,ans=0;
	scanf("%d",&N);
	while(1)
	{
		scanf("%d%d%d",&x,&y,&z);
		if(x==0&&y==0&&z==0)
		break;
		a[x][y]=z;
	}
	while(l<2)
	{
	for(i=1;i<=N;i++)
	{for(j=1;j<=N;j++)
	{
		if(i==1&&j==1)
		{
			f[i][j]=a[i][j];
			if(a[i][j]!=0)
			{
				q[i][j][0][0]++;
			    q[i][j][q[i][j][0][0]][0]=i;
			    q[i][j][q[i][j][0][0]][1]=j;
			}
		}
		else if(i==1&&j>1)
		{
			f[i][j]=f[i][j-1]+a[i][j];
			q[i][j][0][0]=q[i][j-1][0][0];
			for(k=1;k<=q[i][j][0][0];k++)
			{
				q[i][j][k][0]=q[i][j-1][k][0];
				q[i][j][k][1]=q[i][j-1][k][1];
			}
			if(a[i][j]!=0)
			{
				q[i][j][0][0]++;
			    q[i][j][q[i][j][0][0]][0]=i;
			    q[i][j][q[i][j][0][0]][1]=j;
			}
		}
		else if(i>1&&j==1)
		{
			f[i][j]=f[i-1][j]+a[i][j];
			q[i][j][0][0]=q[i-1][j][0][0];
			for(k=1;k<=q[i][j][0][0];k++)
			{
				q[i][j][k][0]=q[i-1][j][k][0];
				q[i][j][k][1]=q[i-1][j][k][1];
			}
			if(a[i][j]!=0)
			{
				q[i][j][0][0]++;
			    q[i][j][q[i][j][0][0]][0]=i;
			    q[i][j][q[i][j][0][0]][1]=j;
			}
		}
		else 
	    {
			if(f[i][j-1]>f[i-1][j])
			{
			f[i][j]=f[i][j-1]+a[i][j];
			q[i][j][0][0]=q[i][j-1][0][0];
			for(k=1;k<=q[i][j][0][0];k++)
			{
				q[i][j][k][0]=q[i][j-1][k][0];
				q[i][j][k][1]=q[i][j-1][k][1];
			}
			}
			else if(f[i][j-1]<=f[i-1][j])
			{
			f[i][j]=f[i-1][j]+a[i][j];
			q[i][j][0][0]=q[i-1][j][0][0];
			for(k=1;k<=q[i][j][0][0];k++)
			{
				q[i][j][k][0]=q[i-1][j][k][0];
				q[i][j][k][1]=q[i-1][j][k][1];
			}	
		    }
			if(a[i][j]!=0)
			{
				q[i][j][0][0]++;
			    q[i][j][q[i][j][0][0]][0]=i;
			    q[i][j][q[i][j][0][0]][1]=j;	
			}
	    } 
	}
	}
	ans+=f[N][N];
	for(i=1;i<=q[N][N][0][0];i++)
	{
		a[q[N][N][i][0]][q[N][N][i][1]]=0;
	}
	l++;
	memset(f,0,sizeof(f)); 
	}
	printf("%d",ans);
    return 0;
}
int c=cc();
int main(){;
}