【移动类DP】三取方格数

Description

设有N*N的方格图，我们将其中的某些方格填入正整数， 而其他的方格中放入0。 某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。 在走过的路上，他取走了方格中的数。（取走后方格中数字变为0） 此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。

Input

第一行:N (4<=N<=50) 接下来一个N*N的矩阵，矩阵中每个元素不大于9，不小于0

Output

一行，表示最大的总和。

Sample Input

4 1234 2134 1234 1324

Sample Output

39

分析

这道题是 方格取数 的加强版，从数据范围来看，开六维数组是肯定会爆掉的，所以我们考虑优化。

和方格取数一样的，我们认为三条路是同时开始找的。

状态设计利用x + y = i + 2（i 为步数，x，y为坐标），可以设计成：f（i, x1, x2, x3），y1, y2, y3可以用状态中的 i 和对应的横坐标算出来。

于是乎就有了状态转移方程：

int y1 = min(i + 2 - x1, n), y2 = min(i + 2 - x2, n), y3 = min(i + 2 - x3, n); int a = max(dp[i - 1][x1 - 1][x2][x3], dp[i - 1][x1][x2 - 1][x3]); int b = max(dp[i - 1][x1][x2][x3 - 1], dp[i - 1][x1 - 1][x2 - 1][x3]); int c = max(dp[i - 1][x1 - 1][x2][x3 - 1], dp[i - 1][x1][x2 - 1][x3 - 1]); int d = max(dp[i - 1][x1][x2][x3], dp[i - 1][x1 - 1][x2 - 1][x3 - 1]); dp[i][x1][x2][x3] = max(max(a, b), max(c, d)) + (k[x1][y1] + k[x2][y2] + k[x3][y3]); //八条路径

当然，和方格取数一样的，我们要对重复计算的点进行处理，如下：

if (x1 == x2) dp[i][x1][x2][x3] -= k[x1][y1]; if (x2 == x3) dp[i][x1][x2][x3] -= k[x2][y2]; if (x1 == x3) dp[i][x1][x2][x3] -= k[x3][y3]; if (x1 == x2 && x2 == x3) dp[i][x1][x2][x3] += k[x1][y1]; //多减了一个要加回来

这样写出来的代码就是这样的：

#include<bits/stdc++.h> using namespace std; int n; char cc; int k[51][51]; int dp[110][51][51][51]; inline int read() { register int x = 0, f = 1; register char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();} return x * f; } int main() { n = read(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> cc; k[i][j] = (cc ^ 48); } } dp[0][1][1][1] = k[1][1]; for (int i = 1; i <= 2 * n - 2; i++) { for (int x1 = 1; x1 <= min(i, n) + 1; x1++) { for (int x2 = 1; x2 <= min(i, n) + 1; x2++) { for (int x3 = 1; x3 <= min(i, n) + 1; x3++) { int y1 = min(i + 2 - x1, n), y2 = min(i + 2 - x2, n), y3 = min(i + 2 - x3, n); int a = max(dp[i - 1][x1 - 1][x2][x3], dp[i - 1][x1][x2 - 1][x3]); int b = max(dp[i - 1][x1][x2][x3 - 1], dp[i - 1][x1 - 1][x2 - 1][x3]); int c = max(dp[i - 1][x1 - 1][x2][x3 - 1], dp[i - 1][x1][x2 - 1][x3 - 1]); int d = max(dp[i - 1][x1][x2][x3], dp[i - 1][x1 - 1][x2 - 1][x3 - 1]); dp[i][x1][x2][x3] = max(max(a, b), max(c, d)) + (k[x1][y1] + k[x2][y2] + k[x3][y3]); if (x1 == x2) dp[i][x1][x2][x3] -= k[x1][y1]; if (x2 == x3) dp[i][x1][x2][x3] -= k[x2][y2]; if (x1 == x3) dp[i][x1][x2][x3] -= k[x3][y3]; if (x1 == x2 && x2 == x3) dp[i][x1][x2][x3] += k[x1][y1]; } } } } printf("%d", dp[2 * n - 2][n][n][n]); return 0; }

然后呢，本蒟蒻介绍一下另外一种教练的写法：

首先，写状态转移的时候在外面套三层for循环，就像这样：

for (int l1 = -1; l1 <= 0; l1++) { for (int l2 = -1; l2 <= 0; l2++) { for (int l3 = -1; l3 <= 0; l3++) { int f1 = x1 + l1, f2 = x2 + l2, f3 = x3 + l3; if (f1 <= 0 || f1 > n || f2 <= 0 || f2 > n || f3 <= 0 || f3 > n) continue; dp[i][x1][x2][x3] = max(dp[i][x1][x2][x3], dp[i - 1][f1][f2][f3] + tmp); } } }

好像是比较简洁QAQ

然后呢，把处理重复计算的那一坨丢到状态转移前面去，也就是说先算出到底要加上多少，然后再利用这个值进行状态转移。

就像这样：

for (int i = 1; i <= n * 2 - 2; i++) { for (int x1 = 1; x1 <= n; x1++) { for (int x2 = 1; x2 <= n; x2++) { for (int x3 = 1; x3 <= n; x3++) { int y1 = i - x1 + 2, y2 = i - x2 + 2, y3 = i - x3 + 2; if (y1 <= 0 || y1 > n || y2 <= 0 || y2 > n || y3 <= 0 || y3 > n) continue; int tmp = k[x1][y1] + k[x2][y2] + k[x3][y3]; if (x1 == x2) tmp -= k[x1][y1]; if (x2 == x3) tmp -= k[x2][y2]; if (x1 == x3) tmp -= k[x3][y3]; if (x1 == x2 && x2 == x3) tmp += k[x1][y1]; } } } }

于是乎，代码就变成了这样：

#include<bits/stdc++.h> using namespace std; int n; char cc; int k[57][57]; int dp[110][57][57][57]; inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();} return x * f; } int main() { n = read(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> cc; k[i][j] = (cc ^ 48); } } dp[0][1][1][1] = k[1][1]; for (int i = 1; i <= n * 2 - 2; i++) { for (int x1 = 1; x1 <= n; x1++) { for (int x2 = 1; x2 <= n; x2++) { for (int x3 = 1; x3 <= n; x3++) { int y1 = i - x1 + 2, y2 = i - x2 + 2, y3 = i - x3 + 2; if (y1 <= 0 || y1 > n || y2 <= 0 || y2 > n || y3 <= 0 || y3 > n) continue; int tmp = k[x1][y1] + k[x2][y2] + k[x3][y3]; if (x1 == x2) tmp -= k[x1][y1]; if (x2 == x3) tmp -= k[x2][y2]; if (x1 == x3) tmp -= k[x3][y3]; if (x1 == x2 && x2 == x3) tmp += k[x1][y1]; for (int l1 = -1; l1 <= 0; l1++) { for (int l2 = -1; l2 <= 0; l2++) { for (int l3 = -1; l3 <= 0; l3++) { int f1 = x1 + l1, f2 = x2 + l2, f3 = x3 + l3; if (f1 <= 0 || f1 > n || f2 <= 0 || f2 > n || f3 <= 0 || f3 > n) continue; dp[i][x1][x2][x3] = max(dp[i][x1][x2][x3], dp[i - 1][f1][f2][f3] + tmp); } } } } } } } printf("%d", dp[2 * n - 2][n][n][n]); return 0; }

不知道为啥这个比我自己写的那个要快一点点QAQ

不过不知道为啥总觉得这代码有些畸形

PS： vijos上面有一道弱化版（1143） 点我点我 ，数据范围是(4 <= n <= 20) 比这道题要弱一些，如果对DP还不太熟练的同学可以先去vijos上刷一刷。

附上 本题链接