这题,最大子矩阵????

P1719 最大加权矩形

WH1KI9RAVE @ 2019-02-12 10:33:58

题都没有看,,,,魔改了最大子矩阵就,过了

#include <bits/stdc++.h>
using namespace std;
int N[505][505];
int m, sum, ans = 0;
int main() {
    memset(N, 0, sizeof(N));
    cin >> m;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> N[i][j];
            N[i][j] += N[i - 1][j];
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = i; j <= m; j++) {
            sum = 0;
            for (int k = 1; k <= m; k++) {
                sum += N[j][k] - N[i - 1][k];
                if (sum < 0)
                    sum = 0;
                ans = max(sum, ans);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

by 142857cs @ 2019-02-12 10:35:11

就是最大子矩阵啊


|