题解 | #[NOIP2000]方格取数#

题目描述：
设有NxN的方格图(N ≤ 10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示(见样例)：

某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
思路：
作为一个dp新手来说，用递推的方式来解这题还是由点难以想到的，于是我就尝试用记忆化搜索来做发现也可以。
1.首先就是用一个四维数组来保存每次计算出的值四维的前两维用来保存第一人的位置，后两维保存第二位的。
2.用dfs遍历两个人每次分别位置取得的最大值。
3.用一个数组记录下最大值
（ps:注意x1+y1==x2+y2并且如果两人到达同一个位置，只能加一次当前位置的值）
AC代码：

#include<bits/stdc++.h>
using namespace std;
int masp[15][15]={0};
int dp[15][15][15][15]={0};
int dfs(int,int,int,int);    
int n;
int main()
{
    cin>>n;
    int a,b,c;
    while(cin>>a>>b>>c){
        if(a==0&&b==0&&c==0)break;
        masp[a][b]=c;
    }
    cout<<dfs(1,1,1,1)<<'\n';
    return 0;
}
int  dfs(int x1,int y1,int x2,int y2)
{
    if (y2+x2!=x1+y1)return 0; 
    if(dp[x1][y1][x2][y2])return dp[x1][y1][x2][y2];
    if(x1==n&&x2==n&&y1==n&&y2==n)return masp[n][n];
    int ans=-1;
    if(x1+1<=n){
        if(x2+1<=n)ans=max(ans,dfs(x1+1,y1,x2+1,y2));
        if(y2+1<=n)ans=max(ans,dfs(x1+1,y1,x2,y2+1));
    }
    if(y1+1<=n){
        if(x2+1<=n)ans=max(ans,dfs(x1,y1+1,x2+1,y2));
        if(y2+1<=n)ans=max(ans,dfs(x1,y1+1,x2,y2+1));
    }
    if(x1==x2&&y1==y2)dp[x1][y1][x2][y2]=ans+masp[x1][y1];
    else dp[x1][y1][x2][y2]=ans+masp[x1][y1]+masp[x2][y2];
    return dp[x1][y1][x2][y2];
}