题目描述

难度分:$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]$。然后分为四种情况进行状态转移：

1. 第一个人从上面过来，第二个人从左边过来，反映到状态上只有$x_1$会变化。状态转移方程为$f[x_1][x_2][k]=f[x_1-1][x_2][k-1]+w$。
2. 第一个人从左边过来，第二个人从上面过来，反映到状态上只有$x_2$会变化。状态转移方程为$f[x_1][x_2][k]=f[x_1][x_2-1][k-1]+w$。
3. 两个人都从上面过来，反映到状态上$x_1$和$x_2$都会变化。状态转移方程为$f[x_1][x_2][k]=f[x_1-1][x_2-1][k-1]+w$。
4. 两个人都从左边过来，反映到状态上$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;
}