C++---线性dp---方格取数（每日一道算法2023.2.25）

注意事项：
本题属于"数字三角形"和"摘花生"两题的进阶版，建议优先看懂那两道，有助理解。

题目：

输入:
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

输出：
67

#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;int const N = 11;
int w[N][N], f[N+N][N][N];  //注意k要开两倍，因为是i+j的总和
int n;int main()
{cin >> n;//接收数据直到“0 0 0”为止int a, b, c;while (cin >> a >> b >> c, a || b || c) w[a][b] = c;//线性dpfor (int k = 2; k<=n+n; k++) {for (int i1 = 1; i1<=n; i1++) {for (int i2 = 1; i2<=n; i2++) {// k = i1+j1 = i2+j2, 切记是相等关系int j1 = k-i1, j2 = k-i2;if (j1 >= 1 && j2 >= 1 && j1 <= n && j2 <= n) {   //判断j1和j2的合法性//如果是重叠点就只加一次，例如(1,2)(1,2), 如果是非重叠点就将两个点都加上，例如(1, 2)(2, 1)int t = w[i1][j1];if (i1 != i2) t += w[i2][j2];//引用节省代码量，分四种情况讨论上两个点如何进行移动int &x = f[k][i1][i2];x = max(x, f[k-1][i1-1][i2-1]);     //down,downx = max(x, f[k-1][i1-1][i2![请添加图片描述](https://img-blog.csdnimg.cn/bd275c5a76dc45349b5cbc3ea8b6aa6d.png)
);       //down,rightx = max(x, f[k-1][i1][i2-1]);       //right,downx = max(x, f[k-1][i1][i2]);         //right, rightx += t;}}}}cout << f[n+n][n][n];return 0;
}

思路：
这道题的难点在于如何将每次一个点的线性dp转变为同时计算两个点
1：将单一点的线性dp跑两次，计算的时候将走过的点进行标注，权重变为0即可。
2：找到点与点的关系，同时计算两个点的dp。

这里我们讲第二种
还是熟悉的y式dp法。

1.状态表示:
f[k][i1][i2]: 从(1, 1)走到(i1, j1) 和 从(1, 1)走到(i2, j2)的最优方案的总和，并且两条线的重复点只能计算一次，属性为Max。

这里的k是表示当 (i1, j1) 和 (i2, j2) 的横纵坐标和 相同时的值。
也就是k = i1+j1 = i2+j2, 因为这样的话，通过k,i1,i2可以推导出j1,j2的值，通过一个量来保存两个量。

这样就很巧妙的解决了标记已使用点的问题，如果两条线走到了相同点，
也就是当i1 = i2, j1 = j2（j1 = k-i1, j2 = k-i2），说明它们在相同点上那么这个点就只计算一次即可，因为数只能取一次。
而当i1 != i2说明状态转移后不在同一个点，那么分别计算w(i1,j1),w(i2,j2)两次。

2.状态计算:
两个点的前一个点向分别向右或下转移，所以有四种情况来讨论：

 f[k-1][i1-1][i2-1] + t   	down,downf[k-1][i1-1][i2] + t     	down,rightf[k-1][i1][i2-1] + t    	right,downf[k-1][i1][i2] + t       	right,right

也就是：f[k][i1][i2] = max(dd, dr, rd, rr)

声明：
算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流

ps：最近要开学啦，恢复更新（假期的我真是懒狗…