<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
1027.方格取数
设有 $N×N$ 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字 0。如下图所示:
某人从图中的左上角 $A$ 出发,可以向下行走,也可以向右行走,直到到达右下角的 $B$ 点。
在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从 $A$ 点到 $B$ 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。
输入格式
第一行为一个整数 $N$,表示 $N×N$ 的方格图。
接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。
行和列编号从 $1$ 开始。
一行“0 0 0”表示结束。
输出格式
输出一个整数,表示两条路径上取得的最大的和。
数据范围
$N \le 10$
错误的贪心思路
首先看到题目,显然有个贪心思路是:先用数字三角形模型做一遍DP,然后在剩下的数里再求一遍DP的贪心思路
数字三角形模型可以参考这篇题解:AcWing 1015.摘花生
可是这种贪心思路是错误的,比如这张图(样例):
3
1 2 1
2 1 2
2 2 2
2 3 2
3 1 1
如果用贪心的思路,先取三个第二行的2,然后只能取一个1
而正解显然是全取完
正解
所以,我们需要改变策略,维护更多的信息
我们还是可以参考AcWing 1015.摘花生的思路,在取一遍时我们维护的是这条路径当前的状态(坐标)
注意题目中说:此人从 $A$ 点到 $B$ 点共走了两次,所以我们可以设两条路径是同时出发的
所以两条路径时很容易想到维护当前两条路径的状态(坐标)也就是 f[x1][y1][x2][y2]
当然,这样做空间复杂度会达到 $n ^ 4$,所以我们需要优化
由我们同时出发的条件,我们注意到:$k = x1 + y1 = x2 + y2$
所以我们可以只用三个维度 f[k][x1][x2]
来维护就行了!(重点),因为 $y1 = k - x1$,$y2 = k - x2$
最后,照葫芦画瓢,按照数字三角形模型将两条路径的转移合并在一起(一共四种)即可解决
c++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 15, M = 2 * N;
int n;//方格图的边长
int w[N][N];
int f[M][N][N];
int get(int i, int j, int k)
{
return max(max(f[k - 1][i - 1][j - 1], f[k - 1][i][j - 1]), max(f[k - 1][i - 1][j], f[k - 1][i][j]));
//转移方程,分成 4 种考虑
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
int x, y, z;
while (cin >> x >> y >> z, x || y || z) w[x][y] += z;
for (int k = 2; k <= 2 * n; ++ k)
for (int i = 1; i <= n; ++ i)
for (int j = 1, v; j <= n; ++ j)
{
if (k - i <= 0 || k - i > n || k - j <= 0 || k - j > n) continue;
f[k][i][j] = get(i, j, k) + w[i][k - i];
if (i != j) f[k][i][j] += w[j][k - j];//!!!
}
cout << f[2 * n][n][n] << endl;
return 0;
}
赞
厉害
basa