寒假集训专题二 K.方格取数

题意：

给一个n*n的方格，从(1,1)到(n,n)，走两次，只能往右或往下，求取得的路径数字和的最大值

思路：

首先想用两次二维的DP解决，发现两个问题

1.求路径的时候把数字化为0不好判断，从终点到起点每次出最大值返回上一个位置存在上一个位置的dp值相同的情况，给解题带来不便。

2.会存在

0	0	2	3	0	0	0
0	0	3	0	0	0	0
0	0	3	0	0	0	0
0	0	0	0	0	0	0
0	0	0	0	4	0	0
0	0	0	0	4	0	0
0	0	3	0	4	0	0
    
0	0		3	0	0	0
0	0		0	0	0	0
0	0		0	0	0	0
0	0	0	0	0	0	0
0	0	0	0		0	0
0	0	0	0		0	0
0	0	3	0		0	0    

可见这两个三在第二次dp中无论如何都无法被算入总情况

两次dp的做法类似贪心，求出局部最优解，但不是整体最优解！

所以我们采用一次性走两次的做法，开四维数组

#include 
const int N=11;
int dp[N][N][N][N];
int a[N][N];
using namespace std;
typedef pair PII;
vector< PII > ve; 
signed main()
{
	int n;
	cin>>n;
	int x,y,z;
	while(~scanf("%d",&x))
	{
		if(x==0) break;
		scanf("%d%d",&y,&z); 
		a[x][y]=z;
	}
	memset(dp,0,sizeof(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++)
				{
					dp[i][j][k][l]=a[i][j]+a[k][l]+max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]));
                    //这里有些吃力，可以这样想，(i，j)(k,l)一定取前一种情况即(i-1,j)(i,j-1)(k-1,l)(k,l-1)所以算起来一共是4种
					if(i==k&&j==l)	//若两个点重复了，则减去，不影响最后的答案
					{
						dp[i][j][k][l]-=a[i][j];
					}
				}
			}
		}
	}
	cout<