洛谷 P1719 最大加权矩形

// P1719 的第 ① 版：枚举四个边界，然后老老实实把里面的数加一遍
//
// 题意的逐字翻译：「找一个大小不限的矩形，使里面所有元素的和最大」
//   ⇒ 上边界 i1、下边界 i2、左边界 j1、右边界 j2 各枚举一遍（四重循环），
//     再用两重循环把这块矩形里的数加起来。⇒ O(n⁶)。
//
// ⚠ n = 120 时这是 **7.6 × 10¹¹** 次加法（正文第 ④ 步有那张表），跑不完。
// ★ 但它仍然要写：它是这一页的标准答案，也是对拍里「一定对」的那一栏。
//
// ⚠⚠ ans 的初值是 **最小的那个数**，不是 0 —— 见 p1719Zero.cpp 那份反例。

#include <bits/stdc++.h>
using namespace std;

int n;
int a[125][125];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];

    int ans = a[1][1];                       // ★ 不是 0：矩形不能为空
    for (int i1 = 1; i1 <= n; i1++)
        for (int i2 = i1; i2 <= n; i2++)
            for (int j1 = 1; j1 <= n; j1++)
                for (int j2 = j1; j2 <= n; j2++) {
                    int sum = 0;
                    for (int i = i1; i <= i2; i++)
                        for (int j = j1; j <= j2; j++) sum += a[i][j];
                    ans = max(ans, sum);
                }
    cout << ans << '\n';
    return 0;
}

// P1719 最大加权矩形 —— 能 AC 的那一版：二维前缀和 + 枚举四个边界
//
// 第 6 章第 13 步那两个式子，原样搬过来：
//   预处理  s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]
//   查询    (i1,j1)~(i2,j2) 的和 = s[i2][j2] - s[i1-1][j2] - s[i2][j1-1] + s[i1-1][j1-1]
//
// 于是「把里面的数加一遍」那两重循环没了：O(n⁶) → O(n⁴)。
// n = 120 ⇒ 枚举 (i1,i2) 和 (j1,j2) 各 7260 种，一共 5271 万次查询，每次四则运算四步。
//
// ⚠ ans 的初值必须是**某个真实存在的数**（这里用 a[1][1]），不能是 0 ——
//   矩阵可以全是负数，那时答案是「最大的那个负数」，而 0 不是任何矩形的和。

#include <bits/stdc++.h>
using namespace std;

int n;
int s[125][125];                             // s[i][j]：左上角 (1,1) 到 (i,j) 的和

int main() {
    cin >> n;
    int first = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            if (i == 1 && j == 1) first = x;
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
        }

    int ans = first;                         // ★ 初值是一个真的存在的矩形（1×1 那个）
    for (int i1 = 1; i1 <= n; i1++)
        for (int i2 = i1; i2 <= n; i2++)
            for (int j1 = 1; j1 <= n; j1++)
                for (int j2 = j1; j2 <= n; j2++) {
                    int sum = s[i2][j2] - s[i1 - 1][j2] - s[i2][j1 - 1] + s[i1 - 1][j1 - 1];
                    ans = max(ans, sum);
                }
    cout << ans << '\n';
    return 0;
}

// 换一把尺子：三种写法各碰了多少下
//
// 用法：./p1719Count <n>        人话版
//       ./p1719Count <n> csv    只打 `键,值`，给 check:viz 用
//
// 数的是同一个动作：「为了知道某个矩形的和，一共动了多少下」——
//   ① 暴力     ：把矩形里每个格子加一遍 ⇒ 所有矩形的面积之和
//   ② 二维前缀和：每个矩形四步四则运算 ⇒ 矩形个数 × 4
//   ③ 枚举上下行 + 最大子段和：每对 (i1,i2) 扫一行 ⇒ 矩形对数 × n
//
// ★ 矩形个数 = C(n+1,2)²（上下边界一对、左右边界一对）。
//   所有矩形的面积之和有闭式：Σ 高 × Σ 宽 = [Σ_{h=1..n} h(n-h+1)]²。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    long long n = (argc > 1) ? atoll(argv[1]) : 120;
    bool csv = (argc > 2 && string(argv[2]) == "csv");
    long long pairs = n * (n + 1) / 2;               // 一维上「选一段」的方案数
    long long rects = pairs * pairs;
    long long spanSum = 0;                           // Σ_{h=1..n} h × (n-h+1)
    for (long long h = 1; h <= n; h++) spanSum += h * (n - h + 1);
    long long brute = spanSum * spanSum;             // 所有矩形的面积之和
    long long fast = rects * 4;
    long long kadane = pairs * n;
    if (csv) {
        printf("n,%lld\nrects,%lld\nbrute,%lld\nfast,%lld\nkadane,%lld\n",
               n, rects, brute, fast, kadane);
    } else {
        printf("n = %lld：一共 %lld 个矩形\n", n, rects);
        printf("① 暴力（逐格加）        %lld 下\n", brute);
        printf("② 二维前缀和（每个 4 步）%lld 下\n", fast);
        printf("③ 上下行 + 最大子段和   %lld 下\n", kadane);
        printf("⇒ ① / ② = %lld 倍，② / ③ = %lld 倍\n", brute / fast, fast / kadane);
    }
    return 0;
}

// P1719 的错法演示：ans 初始化成 0
//
// 除了这一处，它和 p1719.cpp 一模一样。
//
// ⚠ 「大小不限」不等于「可以是空的」：矩形至少要有一个格子。
//   矩阵全是负数时，答案是**最大的那个负数**，而这一版会输出 0 —— 0 不是任何矩形的和。
//
// ★★ 样例挡不住它（样例答案 15 > 0）。
// ★★★ 而对拍抓不抓得到，取决于生成器把 n 造多大（实测，正文第 ⑤ 步）：
//   随机 n <= 6      —— 300 轮抓 **23** 次（n = 1、2 时「全负」随手就有）
//   随机 n = 30..120 —— 300 轮抓 **0** 次（0.5^(n²) 已经是天文数字分之一）
//   专造全负         —— 300 轮抓 **300** 次
//   ⇒ 小数据不是「凑合」，**小本身就是一种覆盖能力**；而要钉死它还得单开一个档位。

#include <bits/stdc++.h>
using namespace std;

int n;
int s[125][125];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
        }
    int ans = 0;                             // ⚠ 就是这里
    for (int i1 = 1; i1 <= n; i1++)
        for (int i2 = i1; i2 <= n; i2++)
            for (int j1 = 1; j1 <= n; j1++)
                for (int j2 = j1; j2 <= n; j2++)
                    ans = max(ans, s[i2][j2] - s[i1 - 1][j2] - s[i2][j1 - 1] + s[i1 - 1][j1 - 1]);
    cout << ans << '\n';
    return 0;
}

// 数据生成器（P1719 对拍用）：`./p1719Gen <seed> [level]`
//
//   level 0（默认）顺手写法：n <= 6，每格随机 -127..127
//   level 1        ★ **全负**：每格随机 -127..-1 —— 专门给「ans 初始化成 0」那版准备的
//   level 2        照着题面规模造：n = 30..120，每格随机 -127..127
//
// ★★★ 三个档位抓「ans 初始化成 0」的成绩是 23 / 300、300 / 300、**0 / 300**（正文第 ⑤ 步），
//   而最值得看的是**档位 0 和档位 2 的对比**：
//   同一种写法（随机填 -127..127），**把 n 造小反而抓得到，照着题面规模造就永远抓不到**。
//   道理很直白：这个 bug 要「整个矩阵全是负数」，概率是 0.5^(n²) ——
//   n = 1、2 时随手就有，n = 120 时是 0.5^14400。
//   ⇒ 对拍的小数据不是「凑合」，**小本身就是一种覆盖能力**；
//     而真要钉死这个 bug，还得单开档位 1。

#include <bits/stdc++.h>
using namespace std;

static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    unsigned seed = (argc > 1) ? (unsigned)atoi(argv[1]) : 1;
    int level = (argc > 2) ? atoi(argv[2]) : 0;
    rng.seed(seed);
    int n = (level == 2) ? ri(30, 120) : ri(1, 6);
    printf("%d\n", n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            printf("%d%c", level == 1 ? ri(-127, -1) : ri(-127, 127), j == n - 1 ? '\n' : ' ');
    return 0;
}