题目描述
难度分:$2000$
输入$n(1 \leq n \leq 300)$和$n$行$n$列的网格图,元素范围$[-1000,1000]$。
你从网格图的左上角出发,每一步只能向右或向下走到相邻的单元格,走到右下角。
然后再从右下角出发,每一步只能向左或向上走到相邻的单元格,走到左上角。
访问到的格子的数字之和最大是多少?重复访问的格子只能统计一次。
输入样例$1$
1
5
输出样例$1$
5
输入样例$2$
2
11 14
16 12
输出样例$2$
53
输入样例$3$
3
25 16 25
12 18 19
11 13 8
输出样例$3$
136
算法
动态规划
其实就是$NOIP$方格取数那道题,思路就是动态规划,唯一的不同在于本题的方格中有负数,注意不能把DP
数组初始化为全$0$数组。把走两次看成是两个人从$(1,1)$位置开始走,每次两人各走一步,但是格子上数字的贡献只能算一次,求两个人殊途同归走到$(n,n)$位置的时候,走过格子数字的最大累加和。
状态定义
$f[x_1][y_1][x_2][y_2]$表示两人从$(1,1)$出发分别到达$(x_1,y_1)$和$(x_2,y_2)$两个位置的最大方格累加和。但是这有个问题,对于本题$n \leq 300$的范围,如果进行四维DP
,是会超时间和空间的,因此要想办法优化掉一维。从$(1,1)$开始枚举几个下一步的位置可以发现规律,在两个人移动的过程中一定会满足$x_1+y_1=x_2+y_2$,因此令$k=x_1+y_1=x_2+y_2$,就可以把状态压缩到三维$f[x_1][x_2][k]$。因此在这个定义下,最终的答案应该是$f[n][n][2n]$。
状态转移
当两个人当前所在格子重合时,本次移动的增量为$w=a[x_1][y_1]$,否则为$w=a[x_1][y_1]+a[x_2][y_2]$。然后分为四种情况进行状态转移:
- 第一个人从上面过来,第二个人从左边过来,反映到状态上只有$x_1$会变化。状态转移方程为$f[x_1][x_2][k]=f[x_1-1][x_2][k-1]+w$。
- 第一个人从左边过来,第二个人从上面过来,反映到状态上只有$x_2$会变化。状态转移方程为$f[x_1][x_2][k]=f[x_1][x_2-1][k-1]+w$。
- 两个人都从上面过来,反映到状态上$x_1$和$x_2$都会变化。状态转移方程为$f[x_1][x_2][k]=f[x_1-1][x_2-1][k-1]+w$。
- 两个人都从左边过来,反映到状态上$x_1$和$x_2$都不会变,只有$k$存在变化。状态转移方程为$f[x_1][x_2][k]=f[x_1][x_2][k-1]+w$。
以上四种情况选择最大的转移即可。
复杂度分析
时间复杂度
由于$k \leq 2n$,因此状态数量为$O(n^3)$。而单次转移最多只需要考虑以上的四种转移来源,因此时间复杂度为$O(1)$。整个算法的时间复杂度为$O(n^3)$。
空间复杂度
空间消耗的瓶颈就是DP
数组,存储了$O(n^3)$级别的状态数量,这也是算法整体的额外空间复杂度。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 301;
int n, a[N][N], f[N<<1][N][N];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
}
}
memset(f, -0x3f, sizeof(f));
for(int k = 2; k <= 2*n; k++) {
for(int x1 = 1; x1 <= n; x1++) {
for(int x2 = 1; x2 <= n; x2++) {
int y1 = k - x1, y2 = k - x2;
if(1 <= y1 && y1 <= n && 1 <= y2 && y2 <= n) {
int w = a[x1][y1];
if(x1 != x2) w += a[x2][y2];
int& x = f[k][x1][x2];
if(k == 2) {
x = w;
}else {
x = max(f[k - 1][x1][x2] + w, x);
x = max(f[k - 1][x1 - 1][x2] + w, x);
x = max(f[k - 1][x1][x2 - 1] + w, x);
x = max(f[k - 1][x1 - 1][x2 - 1] + w, x);
}
}
}
}
}
printf("%d\n", f[n + n][n][n]);
return 0;
}