题目描述

难度分:$1500$

输入$n(2 \leq n \leq 200)$和$n$行$n$列的矩阵$a$，元素范围$[0,10^9]$。

你从左上角出发，要到达右下角。

• 你只能向右/向下走。
• 如果你走到最右一列，再向右走，可以回到同行的第一列。
• 如果你走到最下一排，再向下走，可以回到同列的第一排。

你不能访问之前走过的格子。

输出路径上的元素和的最大值。

输入样例$1$

2
1 2
3 4

输出样例$1$

8

输入样例$2$

3
10 10 10
10 0 10
10 10 10

输出样例$2$

80

算法

构造

这个题的数据范围具有一定欺骗性，本来看$n \leq 200$觉得应该是最短路之类的算法。但是如果用$Floyd$算法的话节点数量在$O(n^2)$规模，时间复杂度会达到$O(n^6)$；如果用$Dijkstra$算法的话，求最短路需要把所有边都取相反数，存在负权；如果用$SPFA$的话，由于是循环矩阵，存在负环，因此排除了最短路的可能性。

由于矩阵中的元素都是非负的，因此我们要尽可能遍历到多的格子，放弃值小的格子。手玩了一下发现规律，可以构造出一个“蛇皮走位”，这个走位只有可能走不到副对角线上的某个格子，其他格子都能遍历到。所以答案就是矩阵的所有元素之和减去副对角线上元素的最小值。

复杂度分析

时间复杂度

双重循环遍历矩阵，求得矩阵上的所有元素之和$tot$，以及矩阵副对角线元素的最小值$mn$。时间复杂度就是遍历矩阵的消耗，为$O(n^2)$。

空间复杂度

除了输入的原始矩阵$a$，仅使用了有限几个变量，因此额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200;
int n, a[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    LL tot = 0;
    int mn = 2e9;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> a[i][j];
            tot += a[i][j];
            if(i + j == n + 1 && a[i][j] < mn) {
                mn = a[i][j];
            }
        }
    }
    cout << tot - mn << '\n';
    return 0;
}