这是我第二次打这篇题解……第一次快写完了tm我给关了 双倍经验：NOIP2000方格取数 这道题其实跟那道方格取数一模一样 好了不扯废话我们开始正式讲解 首先，我们的第一个问题就是：怎么简化问题 题目中说纸条要从左上到右下从右下到左上各传一次，并且只能下右走和上左走 那么我们就可以把它看做是两张纸条从左上到右下 那么就满足dp的基本前提：最优化原理和无后效性 由于我不会压维，所以我就不讲了 那我们该怎么写状态转移方程？ 第一，能不能一遍动规走完再来一遍？ 不行，你自己设一套数据就行了 这种做法实质上是披着dp的贪心 你取了两次的最大值相加，但有可能两次都不取最大值相加的和反而更大！ 那么我们该怎么写？ 让这两张纸条同时开始传！ 首先开个四维数组dp[i][j][h][k]表示第一张纸条到(i,j),第二张纸条到(h,k)所取得的最大值，那么dp[n ][m][n][m]即为答案 状态转移方程很好得到：

dp[i][j][h][k]=max(max(dp[i-1][j][h-1][k],dp[i][j-1][h][k-1]),max(dp[i-1][j][h][k-1],dp[i][j-1][h-1][k]))+a[i][j]+a[h][k];

你可以尝试着把它与数字金字塔那个一起理解， 其实就是四种情况，第一张和第二张纸条从左边过来大还是从上边过来大 但是（i,j）（h,k）很显然不能重合 那么我们就需要去重：

if(i==h&&j==k) dp[i][j][h][k]-=a[i][j];

既然状态转移方程有了，那么直接用个四重循环枚举就好了 OK解决！ 下面完整代码：

#include<bits/stdc++.h>
using namespace std;
int a[51][51];
int dp[51][51][51][51];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
    	{
    		for(int h=1;h<=n;h++)
    		{
    			for(int k=1;k<=m;k++)
    			{
    				dp[i][j][h][k]=max(max(dp[i-1][j][h-1][k],dp[i][j-1][h][k-1]),max(dp[i-1][j][h][k-1],dp[i][j-1][h-1][k]))+a[i][j]+a[h][k];
    				if(i==h&&j==k) dp[i][j][h][k]-=a[i][j];
				}
			}
		}
	}
	cout<<dp[n][m][n][m];
	return 0;
}