洛谷 P1216 [IOI 1994 / USACO1.5] 数字三角形

// 数字三角形 —— 暴力：纯递归，每条路都走一遍
//
// 输入：第一行 n，接下来 n 行，第 i 行有 i 个整数
// 输出：从顶端走到底端，每步只能走到「正下方」或「右下方」，路径上数字之和的最大值
//
// 例如：
//        7
//      3   8
//    8   1   0
//  2   7   4   4
// 最大和是 7 + 3 + 8 + 7 = 25
//
// 这个递归写得非常自然，几乎是把题目念了一遍：
//   best(i,j) = 从格子 (i,j) 出发走到底，能拿到的最大和
//             = a[i][j] + max( best(i+1, j), best(i+1, j+1) )
// 出口：最后一行哪儿也去不了，best = a[i][j] 自己。
//
// 思路完全正确。问题是它慢得离谱：每个格子都要往下分出两个叉，
// 一共 2^(n-1) 条路径，总调用次数是 2^n - 1。
// n = 30 时是十亿七千万次 —— 而这个三角形一共才 465 个格子。
//
// 慢在哪？慢在「重复计算」。看 best(2,1)：
//   从 (0,0) 走到 (2,1) 有两条路（先左后右、先右后左），
//   于是 best(2,1) 会被完完整整地重算两遍。
//   而它下面的每个格子，又会因此被多算一倍……越往下重复得越离谱。
// 拿 trace.cpp 跑一下，你能亲眼看到每个格子被调用了多少次 —— 正好是一个杨辉三角。

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

int n;
vector<vector<long long>> a;

long long best(int i, int j) {
    if (i == n - 1) return a[i][j];                    // 出口：已经在最后一行
    return a[i][j] + max(best(i + 1, j), best(i + 1, j + 1));
}

int main() {
    if (!(cin >> n)) return 0;
    a.assign(n, {});
    for (int i = 0; i < n; i++) {
        a[i].resize(i + 1);
        for (int j = 0; j <= i; j++) cin >> a[i][j];
    }

    cout << best(0, 0) << "\n";
    return 0;
}

// 数字三角形 —— 记忆化搜索
//
// 和 brute.cpp 解同一道题，答案必须一样。
// 但 n = 27 时暴力要跑一秒多，它只要几微秒。
//
// 关键的那一步想法 —— 而且这一步小得让人不敢相信：
//
//   best(i,j) 的答案，只跟 (i,j) 有关。
//   不管你是从哪条路摸到 (2,1) 的，best(2,1) 永远是同一个数。
//   既然如此，第一次算出来之后把它记下来，
//   下次再问到 (2,1)，直接把记下的值还回去就行了 —— 不用再往下递归。
//
//   于是每个格子最多只会被真正计算一次。
//   格子一共 n(n+1)/2 个，所以复杂度从 O(2^n) 一下掉到 O(n²)。
//
// 相比 brute.cpp，代码只多了三行：一个 f 数组、一个 vis 数组、一个「查表就返回」。
// 算法思想没变，递归结构没变，改的只是「别重复算」。
//
// 这就是「记忆化搜索」，它是从递归通向动态规划的那座桥：
//   你先按最自然的方式写出递归（这一步靠的是把题目念清楚），
//   再加一张表把结果存起来（这一步是纯机械的）。
//   等你熟练之后，会发现把递归改写成「从底往上填表」的循环，就是所谓的 DP。
//   但顺序永远是：先会递归，再会记忆化，最后才是 DP。反过来学，必卡。

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

int n;
vector<vector<long long>> a;
vector<vector<long long>> f;      // f[i][j] = best(i,j) 算出来的结果
vector<vector<char>> vis;         // vis[i][j] = 这一格算过了没有

long long best(int i, int j) {
    if (vis[i][j]) return f[i][j];      // ★ 查表命中，直接还回去，不再往下递归

    long long res;
    if (i == n - 1) res = a[i][j];                                    // 出口
    else res = a[i][j] + max(best(i + 1, j), best(i + 1, j + 1));     // 和暴力一模一样

    vis[i][j] = 1;                      // ★ 算完之后才记下来
    f[i][j] = res;
    return res;
}
// 记忆化的标准骨架就是这三段：开头查表 → 中间照抄暴力 → 结尾存表。
// 注意「存表」要放在算完之后，不要放在算之前 —— 养成这个习惯，
// 以后遇到状态之间可能互相依赖的题目才不会踩坑。

int main() {
    if (!(cin >> n)) return 0;
    a.assign(n, {});
    for (int i = 0; i < n; i++) {
        a[i].resize(i + 1);
        for (int j = 0; j <= i; j++) cin >> a[i][j];
    }
    f.assign(n, vector<long long>(n + 1, 0));
    vis.assign(n, vector<char>(n + 1, 0));

    cout << best(0, 0) << "\n";
    return 0;
}

// P1216 的**错法**：记忆化省掉了 `vis` 数组 —— 用「`f[i][j] != 0` 就算算过了」当标记。
//
// 本章正文说记忆化「只多了三行：一个 f 数组、一个 vis 数组、一个查表就返回」。
// 很多人会想省掉那个 `vis`：反正没算过的时候 `f` 是 0，算过之后是个正数，
// **拿 0 当「还没算过」不就行了？**
//
// ⚠⚠ 这道题**不行**，而理由就写在题面里：**「其他输入在 [0, 100] 范围内」——
//   允许 0**。于是一格的答案真的可能是 0（一条全 0 的路），
//   而这一版会把它当成「还没算过」，**每次问到都重算一遍**。
//
// ★★★ 它最难缠的地方是：**答案永远是对的**。
//   重算得到的还是同一个 0，输出一个字节都不差 —— **对拍一辈子抓不到**。
//   它坏的只有复杂度：最坏（整个三角形全是 0）直接退回 `O(2ⁿ)`。
//   ⇒ 这一类 bug 只能靠**数调用次数**或者秒表现形，页面第 ④ 步量了那条曲线。

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

static int n;
static vector<vector<long long>> a, f;
static long long calls = 0;

static long long best(int i, int j) {
    calls++;
    if (f[i][j] != 0) return f[i][j];        // ★ 错在这里：0 既是「没算过」也是一个合法答案
    long long res;
    if (i == n - 1) res = a[i][j];
    else res = a[i][j] + max(best(i + 1, j), best(i + 1, j + 1));
    f[i][j] = res;
    return res;
}

int main(int argc, char** argv) {
    if (!(cin >> n)) return 0;
    a.assign(n, {});
    for (int i = 0; i < n; i++) {
        a[i].resize(i + 1);
        for (int j = 0; j <= i; j++) cin >> a[i][j];
    }
    f.assign(n, vector<long long>(n + 1, 0));
    cout << best(0, 0) << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "calls=" << calls << "\n";
    return 0;
}

// P1216 的递推版（自底向上填表）—— 本章第 10 步说的「这就是 DP」，写出来就是它。
//
// 记忆化是「从上往下问，问到底再往回填」；递推是「从底往上填，填到顶就是答案」。
// 两者**填的是同一张表**，只是顺序反了过来，而且递推**没有递归**：
//
//     f[n-1][j] = a[n-1][j]
//     f[i][j]   = a[i][j] + max(f[i+1][j], f[i+1][j+1])
//     答案      = f[0][0]
//
// ★ 这道题 `r ≤ 1000`，两种写法都能过。递推的好处只有一个，而且和速度无关：
//   **它没有递归深度**。记忆化那版的栈深就是 `r`，题面给到 1000 还很安全，
//   可要是哪天题面给到 10⁶，先炸的是栈不是时间（第 45 章那一章讲的就是这件事）。
//
// ⚠ 顺带一个只在**自顶向下**那种递推里才有的坑：
//   如果反过来写成「f[i][j] = 从顶走到 (i,j) 的最大和」，
//   那么答案是**最后一行的最大值**，不是 f[n-1][0] —— 题面写的是「到底部**任意处**结束」。
//   自底向上这个方向没有这个坑：f[0][0] 就是答案。

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

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<vector<long long>> a(n);
    for (int i = 0; i < n; i++) {
        a[i].resize(i + 1);
        for (int j = 0; j <= i; j++) cin >> a[i][j];
    }
    vector<long long> f(a[n - 1].begin(), a[n - 1].end());
    for (int i = n - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++) f[j] = a[i][j] + max(f[j], f[j + 1]);
    cout << f[0] << "\n";
    return 0;
}

// P1216 的度量程序 —— 这一页所有数字都出自这一份，
// ★ 其中第 ① 段是**回头查第 17 章正文**：那一章的四组数字此前一条断言都没有。
//
// `./p1216Count`      人看的版本
// `./p1216Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 四段：
//   ① ★ 查正文：纯递归的调用次数是不是正好 `2ⁿ - 1`、每个格子是不是正好被调用 `C(i,j)` 次、
//      `n = 20` 最热的那格是不是 92378、正文那三个「白算的比例」对不对；
//   ② ★★★ 「省掉 vis」那个错法的调用次数，随**零的比例**怎么走；
//   ③ ★ 它的答案和正解逐字节相同 —— 对拍 0 次，只能靠数次数；
//   ④ 顶格 `r = 1000`：记忆化只要 500500 次，而纯递归是一个 302 位数。

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

static bool CSV = false;
static void row(const char* key, const vector<long long>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (long long x : v) printf(",%lld", x);
    printf("\n");
}

static int n;
static vector<vector<long long>> a, f;
static vector<vector<char>> vis;
static vector<vector<long long>> hit;        // 每个格子被调用了几次
static long long calls;

/** mode 0 = 纯递归；1 = 记忆化（带 vis）；2 = 省掉 vis（拿 0 当「没算过」） */
static long long best(int i, int j, int mode) {
    calls++;
    hit[i][j]++;
    if (mode == 1 && vis[i][j]) return f[i][j];
    if (mode == 2 && f[i][j] != 0) return f[i][j];
    long long res;
    if (i == n - 1) res = a[i][j];
    else res = a[i][j] + max(best(i + 1, j, mode), best(i + 1, j + 1, mode));
    if (mode == 1) vis[i][j] = 1;
    if (mode) f[i][j] = res;
    return res;
}

static long long run(int mode, long long& outCalls) {
    f.assign(n, vector<long long>(n + 1, 0));
    vis.assign(n, vector<char>(n + 1, 0));
    hit.assign(n, vector<long long>(n + 1, 0));
    calls = 0;
    long long r = best(0, 0, mode);
    outCalls = calls;
    return r;
}

/** 造一个三角形（和 p1216Gen.cpp 逐字一致）。 */
static void gen(int seed, int layers, int zeroPct, int zeroRows = 0) {
    mt19937 rng((unsigned)seed * 2654435761u + 17u);
    n = layers > 0 ? layers : (int)(rng() % 8 + 5);
    a.assign(n, {});
    for (int i = 0; i < n; i++) {
        a[i].resize(i + 1);
        for (int j = 0; j <= i; j++)
            a[i][j] = (i >= n - zeroRows || (int)(rng() % 100) < zeroPct) ? 0 : (int)(rng() % 101);
    }
}

int main(int argc, char** argv) {
    CSV = (argc > 1 && string(argv[1]) == "csv");

    /* ① ★ 回头查第 17 章正文 */
    {
        if (!CSV) printf("① 查第 17 章正文：纯递归的调用次数 / 杨辉三角 / 白算的比例\n");
        vector<long long> out;
        for (int L : {10, 20, 30}) {
            gen(1, L, 0);
            long long c;
            run(0, c);                           // 纯递归
            long long cells = (long long)L * (L + 1) / 2;
            // 正文写「调用次数正好是 2ⁿ - 1」
            long long pow2 = (1LL << L) - 1;
            // 白算的比例（万分之几，取整到小数点后四位 × 10000）
            long long wasteE6 = (c - cells) * 1000000LL / c;
            out.push_back(c); out.push_back(pow2); out.push_back(cells); out.push_back(wasteE6);
            if (!CSV) printf("  n = %2d：格子 %lld 个，调用 %lld 次（2ⁿ-1 = %lld），白算 %.6f%%\n",
                             L, cells, c, pow2, (c - cells) * 100.0 / c);
        }
        row("text", out);

        // 正文写「位置 (i,j) 恰好被调用了 C(i,j) 次」，以及「n = 20 最热的格子 92378 次」
        gen(1, 20, 0);
        long long c;
        run(0, c);
        long long bad = 0, hottest = 0;
        vector<vector<long long>> C(20, vector<long long>(20, 0));
        for (int i = 0; i < 20; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) C[i][j] = C[i - 1][j - 1] + (j <= i - 1 ? C[i - 1][j] : 0);
            for (int j = 0; j <= i; j++) {
                if (hit[i][j] != C[i][j]) bad++;
                hottest = max(hottest, hit[i][j]);
            }
        }
        if (!CSV) printf("  ★ 每个格子的调用次数 ≡ C(i,j)：对不上的有 %lld 个；最热的一格 %lld 次\n",
                         bad, hottest);
        row("pascal", {bad, hottest});
    }

    /* ② ★★★ 「省掉 vis」的调用次数，随零的比例怎么走 */
    {
        if (!CSV) printf("\n② 「省掉 vis」那个错法：20 层三角形，零的比例一档一档往上加\n");
        vector<long long> out;
        for (int z : {0, 10, 30, 50, 70, 90, 100}) {
            gen(1, 20, z);
            long long cOk, cBad;
            run(1, cOk);
            run(2, cBad);
            out.push_back(cBad);
            if (!CSV) printf("  零占 %3d%%：记忆化 %lld 次，省掉 vis %lld 次（%.1f 倍）\n",
                             z, cOk, cBad, cBad * 1.0 / cOk);
        }
        row("zeroCurve", out);
    }

    /* ②' ★★★ 真正的触发条件：底部连续 k 行全 0（草稿以为是「零的比例」，猜错了） */
    {
        if (!CSV) printf("\n②' 换一个旋钮：20 层三角形，**底部 k 行全 0**\n");
        vector<long long> out;
        for (int k : {0, 1, 2, 3, 5, 8, 12, 20}) {
            gen(1, 20, 0, k);
            long long cOk, cBad;
            run(1, cOk);
            run(2, cBad);
            long long zeros = 0;
            for (int i = 0; i < n; i++) for (int j = 0; j <= i; j++) if (a[i][j] == 0) zeros++;
            out.push_back(cBad);
            if (!CSV) printf("  底部 %2d 行全 0（零占 %.1f%%）：记忆化 %lld 次，省掉 vis %lld 次（%.1f 倍）\n",
                             k, zeros * 100.0 / 210, cOk, cBad, cBad * 1.0 / cOk);
        }
        row("rowCurve", out);
    }

    /* ③ ★ 答案完全相同 —— 对拍抓不到 */
    {
        int diff = 0;
        for (int s = 1; s <= 300; s++) {
            gen(s, 0, 0);
            long long c1, c2;
            if (run(1, c1) != run(2, c2)) diff++;
        }
        int diffZ = 0;
        for (int s = 1; s <= 300; s++) {
            gen(s, 12, 60);                      // ★ 连「零很多」那一档也一样对
            long long c1, c2;
            if (run(1, c1) != run(2, c2)) diff += 0, diffZ += (run(1, c1) != run(2, c2));
        }
        if (!CSV) printf("\n③ 答案对不对：默认档 300 轮不一致 %d 次；零占 60%% 那档 300 轮不一致 %d 次\n",
                         diff, diffZ);
        row("same", {diff, diffZ});
    }

    /* ④ 顶格 r = 1000 */
    {
        long long cells = 1000LL * 1001 / 2;
        // 2^1000 的十进制位数
        int digits = (int)floor(1000 * log10(2.0)) + 1;
        if (!CSV) printf("\n④ 顶格 r = 1000：记忆化最多算 %lld 个格子；"
                         "而纯递归要 2¹⁰⁰⁰ - 1 次调用 —— 那是一个 %d 位数\n", cells, digits);
        row("full", {cells, digits});
    }
    return 0;
}

// P1216 对拍生成器：`./p1216Gen <seed> [层数] [零的百分比] [底部全 0 的行数]`
//   层数       默认 5 ~ 12
//   零的百分比 随机撒零，默认 0
//   ★★★ 底部全 0 的行数 —— **这个旋钮才是这一页的全部**
//
// 题面写的是「其他输入在 [0, 100] 范围内」——**0 是合法的**。
// 而顺手写的生成器几乎都是 `rng() % 101`，于是零只占 1% 左右。
//
// ★★★ 这一页要抓的那个 bug（`p1216Zero.cpp`：省掉 vis、拿 0 当「没算过」）
//   **答案永远是对的**，所以它在对拍里是**精确的 0**，加多少轮都没用。
//   它只坏复杂度 —— 而「坏多少」由什么决定，我猜错了一次：
//
//   ⚠ 草稿以为是**零的比例**。实测：20 层里随机撒 90% 的零，调用次数只从 381 涨到 599（1.6 倍），
//     只有撒到 **100%** 才炸（1048575 次）。
//   ★★★ 真正的触发条件是**「底部连续 k 行全是 0」**：`best(i,j) = 0` 要求
//     **(i,j) 下面那一整个三角锥全是零**（因为值都非负，max 为 0 意味着两个儿子都为 0）。
//     ⇒ 底部 k 行全 0 时调用次数大约是 `2^k`，实测 k = 3/5/8/12 依次是 511 / 1141 / 6253 / 65577。
//   ⚠⚠ 而「底部 12 行全 0」那一档零只占 **82.9%**，**比随机撒 90% 的零还少**，
//     却比它炸得多 **110 倍** —— **零的位置比零的比例重要得多。**

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

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    mt19937 rng(seed * 2654435761u + 17u);
    int n = argc > 2 ? atoi(argv[2]) : (int)(rng() % 8 + 5);
    int zeroPct = argc > 3 ? atoi(argv[3]) : 0;
    int zeroRows = argc > 4 ? atoi(argv[4]) : 0;
    n = max(1, min(1000, n));
    zeroPct = max(0, min(100, zeroPct));
    zeroRows = max(0, min(n, zeroRows));

    printf("%d\n", n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            int v = (i >= n - zeroRows || (int)(rng() % 100) < zeroPct) ? 0 : (int)(rng() % 101);
            printf("%d%c", v, j == i ? '\n' : ' ');
        }
    }
    return 0;
}