动态规划DP 数字三角型模型方格取数（题目详解+C++代码实现）

方格取数

原题链接

AcWing 1027. 方格取数

题目描述

设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。
如下图所示：

某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。
在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

输入格式
第一行为一个整数N，表示 N×N 的方格图。
接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。
行和列编号从 1开始。
一行“0 0 0”表示结束。

输出格式
输出一个整数，表示两条路径上取得的最大的和。

数据范围
N≤10

输入样例：

输出样例：

题目分析

与 摘花生 类似，不同点在于该题方格取数要找出两条路径，使其和最大。
回忆 摘花生 动态规划数字三角形模型思考。

摘花生（只走一次）：
$f [i, j]$ 表示左右从 $(1, 1)$ 走到 $(i, j)$ 的路径的最大值
$f [i, j] = ma x (f [i - 1, j] + w [i] [j], f [i, j - 1] + w [i, j])$

方格取数（走两次）：
利用摘花生的思想，同时维护两条路径，用 $f [i 1, j 1, i 2, j 2]$ 表示所有从 $(1, 1), (1, 1)$ 分别走到 $(i 1, j 1), (i 2, j 2)$ 的路径的最大值。

同时，每走一格，要么是 $i + 1$ ，要么是 $j + 1$ ，并且由于是同时出发的两条路径，则一定满足** $i 1 + j 1 = i 2 + j 2$ ** 。据此，我们可以化简状态 $f [i 1, j 1, i 2, j 2]$ ，令 $k = i 1 + j 1 = i 2 + j 2$ ，表示两条路径走到的格子的横纵坐标之和。
$f [k, i 1, i 2]$ 表示所有从 $(1, 1), (1, 1)$ 分别走到 $(i 1, k - i 1), (i 2, k - i 2)$ 的路径的最大值。

但需要注意的是，当两条路径走到同一个格子时，一个方格中的数字只能被取一次，则如何处理“同一个格子不能被重复选择”？
我们知道，只有在 $i 1 + j 1 = i 2 + j 2$ 时，两条路径的格子才可能重合。即为在同一个 $k$ 下，同时满足 $i 1 = i 2$ 时，两条路径的格子重合。此时，该方格内的数字只被加一次。

状态计算

用 $t$ 表示下一步需要取的数字之和，
若两条路径不重合，则 $t = w [i 1] [j 1] + w [i 2] [j 2]$ ，
若两条路径重合，则 $t = w [i 1] [j 1]$ （只用加一次）。

状态的转移计算示意图如下：
路径从左至右：则由 $i - 1$ 至 $i$ ，由 $k - 1$ 至 $k$ 。
路径从上至下：则 $i$ 不变，由 $k - 1$ 至 $k$ 。
在这里插入图片描述

第一条路径：从左至右；第二条路径：从左至右：
$f [k] [i 1] [i 2] = ma x (f [k] [i 1] [i 2], f [k - 1] [i 1 - 1] [i 2 - 1] + t)$
第一条路径：从左至右；第二条路径：从上至下：
$f [k] [i 1] [i 2] = ma x (f [k] [i 1] [i 2], f [k - 1] [i 1 - 1] [i 2] + t)$
第一条路径：从上至下；第二条路径：从上至下：
$f [k] [i 1] [i 2] = ma x (f [k] [i 1] [i 2], f [k - 1] [i 1] [i 2] + t)$
第一条路径：从上至下；第二条路径：从左至右：
$f [k] [i 1] [i 2] = ma x (f [k] [i 1] [i 2], f [k - 1] [i 1] [i 2 - 1] + t)$

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=15;
int n;
int w[N][N];  //权重
int f[N*2][N][N];  //状态计算
int main(){
    scanf("%d",&n);
    int a,b,c;
    while(cin>>a>>b>>c,a||b||c) w[a][b]=c;
    for(int k=2;k<=n+n;k++){
        for(int i1=1;i1<=n;i1++){
            for(int i2=1;i2<=n;i2++){
                int j1=k-i1,j2=k-i2;
                if(j1>=1&&j1<=n&&j2>=1&&j2<=n){  //j符合条件
                    int t=w[i1][j1];  //第一条路径
                    if(i1!=i2) t+=w[i2][j2];  //如果第二条路径与第一条路径重合，则权重w[i][j]不能重复增加
                    int &x=f[k][i1][i2];  //使用&简化代码
                    x=max(x,f[k-1][i1-1][i2-1]+t);  //第一条路径：来自上方；第二条路径：来自上方
                    x=max(x,f[k-1][i1-1][i2]+t);  //第一条路径：来自上方；第二条路径：来自左方
                    x=max(x,f[k-1][i1][i2]+t);  //第一条路径：来自左方；第二条路径：来自左方
                    x=max(x,f[k-1][i1][i2-1]+t);  //第一条路径：来自左方；第二条路径：来自上方
                }
            }
        }
    }
    printf("%d\n",f[n+n][n][n]);
    return 0;
}