1 条题解

  • 0
    @ 2023-9-14 14:33:00
    #include <bits/stdc++.h>
    using namespace std;
    int n;
    int a[125][125];
    int sum[125][125]; // sum[i][j] = sum(a[1][1]~a[i][j])
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cin >> a[i][j];
        // 预处理 sum[i][j]
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                sum[i][j] = sum[i - 1][j] +
                            sum[i][j - 1] +
                            (-sum[i - 1][j - 1]) +
                            a[i][j];
        // 枚举子矩形(左上角 (x,y) 右下角 (xx,yy))
        int ans = a[1][1];
        for (int x = 1; x <= n; x++)
            for (int y = 1; y <= n; y++)
                for (int xx = x; xx <= n; xx++)
                    for (int yy = y; yy <= n; yy++)
                    {
                        int now = sum[xx][yy] +
                                  (-sum[xx][y - 1]) +
                                  (-sum[x - 1][yy]) +
                                  sum[x - 1][y - 1];
                        ans = max(ans, now);
                    }
        cout << ans << "\n";
        return 0;
    }
    
    • 1

    信息

    ID
    1328
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    6
    已通过
    5
    上传者