贵州省建设厅考证官方网站,网店美工培训教程,网站持有者和备案企业,html网站优化注意事项#xff1a; 本题属于数字三角形和摘花生两题的进阶版#xff0c;建议优先看懂那两道#xff0c;有助理解。
题目#xff1a;
输入:
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输出#xff1a;
67#include cm…注意事项 本题属于数字三角形和摘花生两题的进阶版建议优先看懂那两道有助理解。
题目
输入:
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[NN][N][N]; //注意k要开两倍因为是ij的总和
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; knn; k) {for (int i1 1; i1n; i1) {for (int i2 1; i2n; i2) {// k i1j1 i2j2, 切记是相等关系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
); //down,rightx max(x, f[k-1][i1][i2-1]); //right,downx max(x, f[k-1][i1][i2]); //right, rightx t;}}}}cout f[nn][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 i1j1 i2j2, 因为这样的话通过k,i1,i2可以推导出j1,j2的值通过一个量来保存两个量。
这样就很巧妙的解决了标记已使用点的问题如果两条线走到了相同点 也就是当i1 i2, j1 j2j1 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最近要开学啦恢复更新假期的我真是懒狗…
