前置知识:
acwing.1027 方格取数(四维dp算法)
思路如下:
四维数组做法与方格取数的四维做法一样,区别在于 n、m。但是方格取数其实可以重复走同一格,只是答案的最优解恰好就是不走重复格子的情况,而此题明确说明不能走同一格。
首先题目说是先从左上角到右下角,再从右下角到左上角,期间不能走重复格,且走过的数值最大。但是可以发现先后顺序并不影响取最大值的结果,甚至一条路线是从左上角到右下角还是从右下角到左上角都无所谓,结果只受路线当中的数值的大小的影响,那么问题就可以变为两人同时从左上角走到右下角,求走过的不重复的路线的最大值。
明确以上问题后就可以用四维dp来做,但是这种做法就不比暴力 dfs 高明多少了,时间复杂度是 $O(n^2 * m^2)$。那么优化思路如下:两个人同时从右或从下方向走,他们每走一格(不论从哪个方向走),其坐标 $i1 + j1$ 的和 与 $i2 + j2$ 的和都是相等的,这种横纵坐标之和相等的两个点用线连起来就会发现其一直是一条斜45°的斜线,如下图所示:
(2,1)与(1,2)、(3,1)与(2,2)、(3,1)与(1,3)
那么原本四维数组原本用来表示两个点纵坐标的维度就可以用表示两个点横纵坐标之和的这一个维度来代替,想得到纵坐标再用 k - 其对应的横坐标 即可(这个维度还可以代替两点的横坐标)。那么状态的定义就跟四维 dp 数组是一样的,$dp[i1][j1][i2][j2]$ 表示从点(1,1)到 点(i1,j1)、点(i2,j2)的最大值。状态定义有了那看状态转移,状态转移与四维dp方法相当,当两人走到 $dp[k][i1][i2]$ 时,需要从右右、右下、下右、下下四种情况中取最大值再加上两点所处坐标对应的数值(两点重复在一个格子里减去其中一个坐标的值即可),结果就是 $dp[n + m][n][n]$。优化后时间复杂度为 $O(n^2*(n+m))$,比优化之前快几十倍。
代码如下:
#include <iostream>
using namespace std;
const int N = 60;
int n, m;
int g[N][N], dp[2 * N][N][N]; // dp[k][i1][i2] 表示的是点(i1,j1)跟点(i2,j2)的横纵坐标之和,以横=3,列=3为例,k最大为6(即右下角点(3,3))),所以根据题目的数据范围需要开到 2N
int main() {
cin >> n >> m; // 这里跟题目中的m、n不一样
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> g[i][j];
for(int k = 2; k <= m + n; k++) // k最小为1(即左上角点(0,1)),但是k=1时看两个点没有意义,所以k从2开始,即初始为走了一步
for(int i1 = 1; i1 <= n; i1++)
for(int i2 = 1; i2 <= n; i2++) {
int j1 = k - i1, j2 = k - i2; // 根据k的定义得出两个点的纵坐标
if(j1 > 0 && j2 > 0) {
int num = g[i1][j1];
if(i1 != i2) num += g[i2][j2]; // 两点未重复,则加上两点对应的数值,重复则需随意减去某一点的数值
int &a = dp[k - 1][i1][i2]; // 右右
int &b = dp[k - 1][i1][i2 - 1]; // 右下
int &c = dp[k - 1][i1 - 1][i2]; // 下右
int &d = dp[k -1][i1 - 1][i2 - 1]; // 下下
dp[k][i1][i2] = max(max(a, c), max(b, d)) + num; // 四种情况选择最大的情况(类似于摘花生模型)+两点的数值
}
}
cout << dp[n + m][n][n] << endl; // 结果就为横纵坐标和最大值与两点横坐标最大值与两点纵坐标最大值(其包含在了k里面)
return 0;
}