记录编号 101153 评测结果 AAAAAA
题目名称 [NOIP 2000]方格取数 最终得分 100
用户昵称 Gravatar高哥 是否通过 通过
代码语言 C++ 运行时间 0.001 s
提交时间 2014-05-10 10:35:40 内存使用 0.32 MiB
显示代码纯文本
//这是一个很傻屄的做法 
#include <iostream>
#include <cstdio>
using namespace std;
int f[30][30],n;
int b[30][30];
void sb(int p,int q)
{
	int a=f[p][q];
	//cout<<a<<endl;
	 if(a==0)
	  return ;
	
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    {
		 if(f[i][j]==a)
		 {
	       	//cout<<i<<' '<<j<<endl;
	        b[i][j]=0;

	     if(f[i-1][j]>f[i][j-1])
	       sb(i-1,j);
	     else
	       sb(i,j-1);
	     return;
	     }
	    }
}
int max(int a,int b)
{
	if(a>b)
	 return a;
	return b;
}
int input()
{
	int x,y,c;
	do
	{
		cin>>x>>y>>c;
		f[x][y]=c;
		b[x][y]=c;
		
	}while(x && y && c);
	
}
int searchf()
{
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    f[i][j]=max(f[i-1][j],f[i][j-1])+f[i][j];
}
int searchb()
{
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    b[i][j]=max(b[i-1][j],b[i][j-1])+b[i][j];
}
int main()
{
	freopen("fgqs.in","r",stdin);
	freopen("fgqs.out","w",stdout);
	cin>>n;
	input();
	searchf();
	sb(n,n);
	searchb();

	cout<<f[n][n]+b[n][n]<<endl;
	return 0;
	
}