P10463 To the Max 题解

Eason_cyx · 2024-05-16 13:42:06 · 题解

首先枚举 i,j，计算每一行的第 i 个数到第 j 个数的和。然后假设整个矩阵的答案矩阵就是从第 i 列到第 j 列，那么这个问题就转换为了给定每一列的这些和（一个数），那就变成了求一维最大子段和。这样就可以找到答案了。而这些数的和使用前缀和处理即可。

时间复杂度 O(n^3)。

#include <bits/stdc++.h>

using namespace std;
int a[505][505],s[505][505],f[505]; //s[j][i]表示第j列的第1~i个数的和
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            cin >> a[i][j];
        }
    }
    for(int j = 1;j <= n;j++) {
        for(int i = 1;i <= n;i++) {
            s[j][i] = s[j][i-1] + a[i][j];
        }
    }
    int ans = -0x7fffffff;
    for(int i = 1;i < n;i++) {
        for(int j = i+1;j <= n;j++) {
            for(int k = 1;k <= n;k++) f[k] = max(f[k-1]+s[k][j]-s[k][i-1],s[k][j]-s[k][i-1]);
            ans = max(ans,*max_element(f+1,f+n+1));
        }
    }
    cout << ans << endl;
    return 0;
}