📚 课堂笔记 — 2026年6月21日

---

🗺️ 专题一：最短路变形（3题）

1. 选择最佳线路 P5978

题意：多起点单终点的最短路。从 $w$ 个起点中选一个，到终点 $s$ 的最短距离。

思路：反向建图 + Dijkstra。把所有边方向反转，从终点 $s$ 跑一次最短路，然后取 $w$ 个起点中 dist 最小的。

💡 为什么反向？ 正向需要跑 $w$ 次Dijkstra，反向只需跑1次！

易错点：

• 多组测试数据，需 while(cin >> n >> m >> s) 读到EOF
• 反向建图：边 p→q 存为 q→p

// 核心：反向建图，从终点跑dijkstra
for (int i = 1; i <= m; i++) {
    cin >> x >> y >> c;
    v[y].push_back({x, c});  // 反向！
}
dijkstra(s);
// 答案 = min(dp[起点i]) for all i

---

2. 电车 P5979

题意：每个路口有开关，默认指向第一条轨道（代价0），其余轨道需切换开关（代价1）。求起点到终点最少切换次数。

思路：0-1 BFS / Dijkstra。默认轨道边权=0，非默认轨道边权=1。

// 第一个轨道权重=0，其余=1
cin >> m;
for (int j = 1; j <= m; j++) {
    cin >> x;
    if (j == 1) v[i].push_back({x, 0});  // 默认，不切换
    else v[i].push_back({x, 1});          // 需要切换
}
// 然后跑Dijkstra

💡 边权只有0和1时，也可用 双端队列BFS（0放队首，1放队尾），比优先队列更快！

---

3. 最优乘车 P3846

题意：$M$ 条巴士线路，$N$ 个站点。同一线路上可从任意站上车、任意站下车。求从站1到站N的最少换乘次数。

思路：建图 + BFS。同一线路上的站点，从前往后连有向边（边权=1表示换乘）。BFS求最短路，换乘次数 = 距离 - 1（或直接BFS距离即为换乘次数）。

建图方式：同一线路上，站点 $a_j$ 可直达 $a_k$（$j < k$），连边 $a_j → a_k$。

// 一条线路读入所有站号后，前面的站连向后面的站
for (int j = 1; j <= cnt; j++)
    for (int k = j + 1; k <= cnt; k++)
        v[b[j]].push_back(b[k]);
// BFS 从1出发，dis[n]-1 即为换乘次数

---

🪨 专题二：区间DP — 石子合并系列（6题）

核心状态转移方程

dp[i][j] = min/max { dp[i][k] + dp[k+1][j] + cost(i,j) }
         对所有 i ≤ k < j

• dp[i][j]：合并区间 [i, j] 的最小/最大得分
• cost(i,j)：区间 [i,j] 内石子总和（前缀和优化）

📐 前缀和优化

s[i] = s[i-1] + a[i];           // 前缀和
cost(i,j) = s[j] - s[i-1];      // 区间和 O(1)

---

4. 合并石子 P2541（线性）

题意：一排 $n$ 堆石子，每次合并相邻两堆，求最小总得分。

最基础的区间DP，环形不需要。

for (int l = 1; l <= n; l++)           // 枚举区间长度
    for (int i = 1; i <= n - l + 1; i++) {  // 枚举左端点
        int j = i + l - 1;             // 右端点
        for (int k = i; k < j; k++)    // 枚举分割点
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
    }
cout << dp[1][n];

---

5. 石子合并（环形）P1324

题意：环形排列，求最小得分 + 最大得分。

破环成链：将数组复制一遍（a[i+n] = a[i]），在长度为 $2n$ 的链上做区间DP，最后取所有长度为 $n$ 的区间的最优值。

// 破环成链
for (int i = 1; i <= n; i++) a[i+n] = a[i];
for (int i = 1; i <= 2*n; i++) s[i] = s[i-1] + a[i];

// 区间DP
for (int l = 2; l <= n; l++)
    for (int i = 1; i <= 2*n - l + 1; i++) {
        int j = i + l - 1;
        for (int k = i; k < j; k++) {
            f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j]-s[i-1]);
            g[i][j] = max(g[i][j], g[i][k] + g[k+1][j] + s[j]-s[i-1]);
        }
    }

// 枚举所有起点，取最优
for (int i = 1; i <= n; i++) {
    ans_min = min(ans_min, f[i][i+n-1]);
    ans_max = max(ans_max, g[i][i+n-1]);
}

💡 破环成链是环形区间DP的标准套路！ 复制数组 + 取所有长度为n的区间。

---

6. 环形石子合并问题 P7344

与P1324基本相同，环形 + 输出最小最大得分。数据范围 $n ≤ 100$。

7. 石子合并（环形）P2542

与P1324/P7344相同，环形 + 最小最大，$n ≤ 400$。

---

8. ⭐ 能量项链 P7358

题意：环形项链，每颗珠子有头标记和尾标记。合并相邻两颗 $(m,r)$ 和 $(r,n)$ 释放能量 $m × r × n$，新珠子为 $(m,n)$。求最大总能量。

状态转移：

dp[i][j] = max { dp[i][k] + dp[k+1][j] + a[i] × a[k+1] × a[j+1] }

💡 关键区别：代价不是区间和，而是 $a[i] × a[k+1] × a[j+1]$（左端点 × 分割点 × 右端点的下一个）。

for (int l = 2; l <= n; l++)
    for (int i = 1; i <= 2*n - l + 1; i++) {
        int j = i + l - 1;
        for (int k = i; k < j; k++)
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + a[i]*a[k+1]*a[j+1]);
    }

⚠️ 姜子钰这道题提交了7次才AC（周立行5次），是最卡的一道。常见错误：转移方程中 $a$ 数组下标写错。

---

🧠 知识点总结

最短路变形解题框架

变形	技巧	本题
多起点单终点	反向建图	P5978
0/1边权	0-1BFS / Dijkstra	P5979
换乘最少	同线路连边 + BFS	P3846

区间DP解题框架

1️⃣ 定义状态 dp[i][j]
2️⃣ 枚举顺序：先短后长（区间长度从小到大）
3️⃣ 枚举分割点 k，转移方程
4️⃣ 环形 → 破环成链（数组翻倍）
5️⃣ 答案：枚举所有起点取最优

⚠️ 今日高频错误

错误	出处	正确做法
环形忘记翻倍数组	P1324/7344/2542	a[i+n] = a[i]
dp初始化不对	全部石子合并	dp[i][i] = 0，其余INF/-INF
getline解析出错	P3846	cin.ignore() 清缓冲区
多组数据不清空	P5978	每组清空vector和vis数组
能量项链下标错	P7358	代价是 a[i]*a[k+1]*a[j+1]

---

📈 今日学习曲线

14:27 ━━━━▶ P5978 选择最佳线路 ✅ （最短路入门）
14:49 ━━━━━▶ P5979 电车 ✅ （0-1最短路）
15:47 ━━━━━━▶ P3846 最优乘车 ✅ （BFS换乘）
16:16 ━━━▶ P2541 合并石子 ✅ （区间DP入门）
16:32 ━━━━▶ P1324 环形石子 ✅ （破环成链）
16:35 ━▶ P7344 环形石子 ✅ （同上巩固）
16:37 ━━━▶ P1567 环形石子 ✅ （只求最大）
16:40 ━▶ P2542 环形石子 ✅ （同上巩固）
17:03 ━━━━━▶ P7358 能量项链 ✅ （区间DP变种）

🔑 核心收获：今天从最短路过渡到区间DP，掌握了两个关键套路——反向建图和破环成链。能量项链是区间DP的进阶应用，代价函数不再是简单的区间和。