方格取数
题目 方格取数
设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。
某人从图中的左上角A出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。
在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。
输入格式
第一行为一个整数N，表示 N×N 的方格图。
接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行,该列上所放的数.
行和列编号分别从1,1开始。
一行“0 0 0”表示结束。
输出格式
输出一个整数,表示两条路径上取得的最大的和
数据范围
N<=10
样例
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
思路分析
起点 (1,1)，终点 (n,n)，每次规定只能向右或向下走
我们可以从起点出发两次，但同一个格子在两次路径中都经过的话，他的物品价值只会被累加 1次
问两次路线，途径格子的物品的总价值最大是多少
题目要求我们从起点先后出发两次
但我们可以规定两次是同时出发的，因为这两种方案的所有路线都是一一对应的
为什么这么映射呢？因为这样子做的话，我们可以轻松的处理两次路线走到同一个格子的情况
由此我们就可以把路径长度，作为DP的阶段
每个阶段中，我们同时把两条路径扩展一步，即路径长度加 1，来进入下一个阶段
而路径长度加1后，无非就是向下走一格或是向右走一格，对应横纵坐标的变换
根据k,x1,y1,x2,y2的关系，我们可以获得如下等式
x1+y1=x2+y2=k
获得上述等式以后，我们就可以通过三个维度来描述状态了，分别是k,x1,x2 于是，状态的初值为f[2][1][1]，目标状态为f[2 * n][n][n]
（用原始的x1,y1 x2,y2也是可以的 但是因为有4维 可能导致效率很低 所以得想一个办法 既能表示出x1,y1和x2,y2又能降低维度 用一个k去记录总步数
（或者说是横纵坐标的总和 因为每次都在往右或往下走 这个总和是会一直加的 且在同一时刻 第一条路径和第二条路径的k是一样大的） 然后就只需要记录x1和x2即可 至于y1,y2可以用k-x1 和k-x2求出 这样一来 能用一个三维的状态数组表示出从起点走到x1,y1和x2,y2的总价值的最大值）
那么对于如何判断两次路线走进了同一个方格里，直接用x1=x2来判断了
当x1≠x2，当前两条路线走到的格子不是同一个，v=w(x1,k−x1)+w(x2,k−x2) 当x1=x2，当前两条路线走到了同一个格子中，则v=w(x1,k−x1)
f[k][i][j]=max({f[k-1][i][j],f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1]})+v;
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 15, M = 2 * N;
int n;
int a, b, c;
int w[N][N];
int f[M][N][N];
int main()
{
cin >> n;
while (cin >> a >> b >> c, a || b || c)
w[a][b] += c;
for (int k = 2; k <= 2 * n; ++ k)
{
for (int i = 1; i < k && i <= n; ++ i)
{
for (int j = 1; j < k && j <= n; ++ j)
{
int v = w[i][k - i];
if (i != j) //判断两条路线是否经过同一个格子 经过的话只需要累加一次
v += w[j][k - j];
f[k][i][j]=max({f[k-1][i][j],f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1]})+v;
}
}
}
cout << f[2 * n][n][n] << endl;
return 0;
}
💬 评论