洛谷 P3406 海底高铁

// P3406 的第 ① 版：每次旅行，沿途一段一段地记一笔
//
// ★ 它能拿分：题面写着「对于 30% 数据 M = 2」和「另外 30% 数据 N, M <= 1000」——
//   两档加起来 **60 分**，而这一版只比正解少一个差分。
//
// ⚠ 满数据 N = M = 1e5、每次都从头走到尾 ⇒ 1e10 次自增，跑不完（正文第 ③ 步有秒表）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> p(m);
    for (int i = 0; i < m; i++) cin >> p[i];

    vector<long long> cnt(n + 2, 0);
    for (int i = 0; i + 1 < m; i++) {
        int l = p[i], r = p[i + 1];
        if (l > r) swap(l, r);
        for (int j = l; j < r; j++) cnt[j]++;         // ← 一段一段地加
    }

    long long ans = 0;
    for (int i = 1; i <= n - 1; i++) {
        long long a, b, c;
        cin >> a >> b >> c;
        ans += min(cnt[i] * a, c + cnt[i] * b);
    }
    cout << ans << '\n';
    return 0;
}

// P3406 海底高铁 —— 能 AC 的那一版：差分统计次数，再每段各自选便宜的
//
// ★ 这道题的「关键的一步」是**拆**：
//   一次旅行 P_j -> P_{j+1} 看着是一件事，但票是**一段一段买**的，
//   而且第 i 段的 IC 卡只能坐第 i 段 ⇒ **N-1 段之间毫无关系**。
//   所以只要知道「第 i 段被走了多少次」，每一段就各自是一道两选一的小题：
//
//       cnt[i] 次都买纸质票： cnt[i] * A[i]
//       买张卡再刷：          C[i] + cnt[i] * B[i]
//       取小的那个。
//
//   ⇒ 一道看起来要「统筹安排」的题，塌成了 N-1 个互不相干的选择题。
//
// 而「第 i 段被走了多少次」正是第 6 章后半场那三行：区间加 1 ⇒ 差分。
//   ⚠ 方向不限：P_j 可能比 P_{j+1} 大，要先 swap 成 [l, r)，
//     经过的是第 l, l+1, …, r-1 段（共 r-l 段），所以差分打在 d[l] += 1、d[r] -= 1。
//
// ⚠⚠ 答案必须 long long：cnt <= 1e5、A <= 1e5 ⇒ 一段最多 1e10，
//   N-1 段加起来 1e15 —— 是 int 上限的**四十七万倍**（不是「差一点」）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> p(m);
    for (int i = 0; i < m; i++) cin >> p[i];

    vector<long long> d(n + 2, 0);
    for (int i = 0; i + 1 < m; i++) {
        int l = p[i], r = p[i + 1];
        if (l > r) swap(l, r);               // ⚠ 方向不限
        d[l] += 1;
        d[r] -= 1;                           // 走的是第 l .. r-1 段
    }

    long long ans = 0, cnt = 0;
    for (int i = 1; i <= n - 1; i++) {
        cnt += d[i];                         // 前缀和还原：第 i 段被走了多少次
        long long a, b, c;
        cin >> a >> b >> c;
        ans += min(cnt * a, c + cnt * b);    // ★ 每段各自选，互不影响
    }
    cout << ans << '\n';
    return 0;
}

// P3406 的错法演示：忘了「方向不限」
//
// 题面写着「乘车每经过两个相邻的城市之间（**方向不限**）」——
// 也就是 P_j 可能**大于** P_{j+1}（往回坐）。
// 少了那句 swap，区间就成了「左端比右端大」，这一趟旅行等于一段都没记。
//
// ★ 这一处**样例挡得住**：样例的第一段旅行就是 3 -> 1（往回坐）。
//   ⇒ 又一次「先跑样例、逐字节比」的价值 —— 前面几页里样例挡不住的坑出现过太多次，
//     以至于容易忘了：**挡得住的那些，只要你真跑了就一分钱不花。**

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> p(m);
    for (int i = 0; i < m; i++) cin >> p[i];

    vector<long long> d(n + 2, 0);
    for (int i = 0; i + 1 < m; i++) {
        int l = p[i], r = p[i + 1];          // ⚠ 少了 if (l > r) swap(l, r);
        d[l] += 1;
        d[r] -= 1;
    }

    long long ans = 0, cnt = 0;
    for (int i = 1; i <= n - 1; i++) {
        cnt += d[i];
        long long a, b, c;
        cin >> a >> b >> c;
        ans += min(cnt * a, c + cnt * b);
    }
    cout << ans << '\n';
    return 0;
}

// P3406 的错法演示：答案用 32 位存
//
// ★ 为什么这份用的是 unsigned 而不是 int（第 45 章那一课）：
//   int 溢出在 C++ 里是**未定义行为** —— 它可能回绕、可能被 -O2 优化成别的样子，
//   换台机器结果就变，**这种数字写不进教材**。
//   换成 unsigned，「超过 2³² 就从头绕」是标准写死的，谁跑都一样。
//   ⇒ 演示错误写法时，要把那个错**钉成可复现的**。
//
// ⚠ 除了 ans 和 cnt 的类型，它和正解一模一样。
//   而**样例挡不住它**：样例答案 6394，连 int 的零头都不到。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> p(m);
    for (int i = 0; i < m; i++) cin >> p[i];

    vector<int> d(n + 2, 0);
    for (int i = 0; i + 1 < m; i++) {
        int l = p[i], r = p[i + 1];
        if (l > r) swap(l, r);
        d[l] += 1;
        d[r] -= 1;
    }

    unsigned ans = 0;                        // ⚠ 32 位（学生真写的是 int，这里见文件头）
    unsigned cnt = 0;
    for (int i = 1; i <= n - 1; i++) {
        cnt += (unsigned)d[i];
        unsigned a, b, c;
        cin >> a >> b >> c;
        ans += min(cnt * a, c + cnt * b);    // ⚠ 这里的乘法也是 32 位的
    }
    cout << ans << '\n';
    return 0;
}

// 数据生成器（P3406 对拍用）：`./p3406Gen <seed> [level]`
//
//   level 0（默认）顺手写法：N <= 8、M <= 8，A/B/C 都是 1..50 的小数
//   level 1        ★ **把答案顶到 32 位装不下**：N、M 拉到几百，A/C 取 1e5 附近、
//                  B 取 A 的一半以上（让卡也省不下多少），旅行都是「从头走到尾」
//
// ★★ 两个档位抓的是**不同的** bug（正文第 ⑤ 步那张表）：
//   忘了 swap 那版，档位 0 一抓一个准（随机的 P 有一半是往回走的）；
//   而 32 位溢出那版，**档位 0 一次都抓不到** —— 小数值算出来的答案只有几千，
//   离 2³² 差着六个数量级。⇒ 生成器的**取值范围**不覆盖，轮数再多也没用
//   （第 5 章 P1042 那条：先写下触发条件，再问生成器造不造得出）。

#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);
    // ⚠ 这两个数是**算过**的：每段的花费约 m×B ≈ 400×7万 = 2.8e7，
    //   乘上 n ≈ 400 段就是 1e10 —— 稳稳超过 32 位能装的 4.29e9。
    //   （第一版写的是 n, m <= 80，答案只到 6e8，**一次都没抓到**，白跑了 300 轮。）
    int n = (level == 1) ? ri(300, 400) : ri(2, 8);
    int m = (level == 1) ? 400 : ri(2, 8);
    printf("%d %d\n", n, m);
    for (int i = 0; i < m; i++) {
        int v = (level == 1) ? ((i & 1) ? n : 1) : ri(1, n);   // 顶格档：来回走全程
        printf("%d%c", v, i == m - 1 ? '\n' : ' ');
    }
    for (int i = 1; i <= n - 1; i++) {
        int a, b, c;
        if (level == 1) { a = ri(90000, 100000); b = ri(a / 2, a - 1); c = ri(90000, 100000); }
        else { a = ri(2, 50); b = ri(1, a - 1); c = ri(1, 50); }
        printf("%d %d %d\n", a, b, c);
    }
    return 0;
}