📝 6月20日 练习笔记

今日练习：最短路 + 区间DP
3 道题，涵盖图论建图技巧、区间DP模板、环形区间DP

---

📋 知识点概览

题目	知识点	难度
选择最佳线路	最短路 + 反向建图	★★★
P981 合并石子	区间DP（线性）
「一本通 5.1 例 1」石子合并	区间DP（环形）

---

一、选择最佳线路

题目

给定 n 个公交站台、m 条单向公交线路。琪琪可以从 w 个始发站中选一个出发，到达终点 s。求最少耗时，无法到达输出 -1。

核心分析

难点：有 w 个可能的起点，如果对每个起点跑一次 Dijkstra，复杂度 O(w × n²)，会超时。

关键技巧——反向建图：

• 正常思路：从每个起点出发跑最短路 → w 次最短路
• 反向思维：从终点 s 出发，在反向图上跑一次最短路，就能得到 s 到所有起点的最短距离
• 反向图：把每条边 p → q 变成 q → p
• 这样跑一次 Dijkstra 就搞定，复杂度 O(n²) ✓

为什么反向建图可行？

• 原图中：起点 u → 终点 s 的最短路
• 反向图中：终点 s → 起点 u 的最短路
• 因为边权不变，反向图上的最短路距离 = 原图上 u → s 的最短路距离

AC 代码（带详细注释）

#include<bits/stdc++.h>
#define int long long
const int INF=1e18;
using namespace std;
int n,m,s,w,x1,x2,x3;
struct st{
    int x,y;  // x=到达节点, y=边权
};
signed main(){
    // 多组数据，读到EOF
    while(cin>>n>>m>>s){
        vector<st> v[1010];    // 邻接表（存反向图）
        int a[1010]={0},T[1010]={0},vis[1010]={0};
        
        // 读入m条边，反向建图
        // 原图：x1 → x2，权x3
        // 反向：x2 → x1，权x3
        for(int i=1;i<=m;i++){
            scanf("%lld%lld%lld",&x1,&x2,&x3);
            v[x2].push_back({x1,x3});  // 注意：存的是反向边！
        }
        
        // 读入w个起点
        cin>>w;
        for(int i=1;i<=w;i++){
            scanf("%lld",T+i);  // T[i]存的是可能的起点编号
        }
        
        // Dijkstra 初始化
        for(int i=1;i<=n;i++){
            a[i]=INF;       // a[i] = s到i的最短距离（反向图上）
        }
        a[s]=0;             // 从终点s出发
        
        // Dijkstra 主循环（O(n²) 朴素版）
        for(int i=1;i<=n;i++){
            int mii=0,mi=INF+1;
            // 找未访问的距离最小的点
            for(int i=1;i<=n;i++){
                if(vis[i]==0&&a[i]<mi){
                    mii=i;
                    mi=a[i];
                }
            }
            vis[mii]=1;     // 标记已确定
            // 松弛相邻边
            for(auto i:v[mii]){
                int t1=i.x,t2=i.y;  // t1=邻居, t2=边权
                if(a[t1]>t2+mi){
                    a[t1]=t2+mi;
                }
            }
        }
        
        // 在w个起点中取最小值
        // a[T[i]] = 反向图上s到T[i]的距离 = 原图上T[i]到s的距离
        int mi=INF;
        for(int i=1;i<=w;i++){
            if(a[T[i]]<mi){
                mi=a[T[i]];
            }
        }
        
        if(mi==INF) cout<<-1<<endl;  // 没有起点能到达s
        else cout<<mi<<endl;
    }
    return 0;
}

易错点

易错	说明
⚠️ 忘记反向建图	正向建图的话，从 s 出发跑最短路得到的是 s 到各点的距离，不是各点到 s 的距离
⚠️ 多组数据不清空	每组数据的 v[]、a[]、vis[] 都要重新初始化（代码中用局部变量自动清零）
⚠️ 朴素 Dijkstra 选点	每轮要找未访问且距离最小的点，注意 vis 检查

💡 一句话

多起点到一个终点 → 反向建图，从终点跑一次最短路

---

二、P981 合并石子（线性区间DP）

题目

一排 n 堆石子，每次只能合并相邻两堆，合并得分为新堆石子数。求合并成一堆的最小总得分。

核心分析

为什么不能用贪心？

• 贪心每次选最小相邻对合并，但合并出的新堆在后续每步都会被重复计入得分
• 越早合并的堆被加的次数越多，需要全局统筹 → 必须用 DP

区间 DP 定义：

• dp[i][j] = 把第 i 堆到第 j 堆合并成一堆的最小得分
• dp[i][i] = 0（一堆不需要合并，得分为0）

状态转移：

• 枚举断点 k（i ≤ k < j），把 [i,j] 拆成 [i,k] 和 [k+1,j]
• dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j))
• 其中 sum(i,j) = a[j] - a[i-1]（前缀和优化）

为什么 + sum(i,j)？

• 最后一步合并时，[i,k] 已经合成一堆（石子数=sum(i,k)），[k+1,j] 也合成一堆（石子数=sum(k+1,j)）
• 合并这两堆的得分 = sum(i,k) + sum(k+1,j) = sum(i,j)

枚举顺序：

• 必须按区间长度从小到大枚举
• 因为大区间的值依赖小区间的值

AC 代码（带详细注释）

#include<bits/stdc++.h>
#define int long long
const int INF=1e18;
using namespace std;
int n,a[110],dp[110][110];
signed main(){
    cin>>n;
    // 初始化：所有dp[i][j]设为INF
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=INF;
        }
    }
    
    // 读入石子，同时计算前缀和
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]+=a[i-1];    // a[i]现在是前缀和：a[i]=a[1]+a[2]+...+a[i]
        dp[i][i]=0;      // 单堆不需要合并，得分为0
    }
    
    // 按区间长度从小到大枚举
    for(int i=2;i<=n;i++){           // i = 区间长度
        for(int j=1;j<=n-i+1;j++){   // j = 区间左端点
            int ed=j+i-1;             // ed = 区间右端点
            // 枚举断点k：把[j,ed]拆成[j,k]和[k+1,ed]
            for(int k=j;k<ed;k++){
                dp[j][ed]=min(dp[j][ed],
                    dp[j][k]+dp[k+1][ed]+a[ed]-a[j-1]);
                //          ↑左半代价  ↑右半代价  ↑合并代价=sum(j,ed)
            }
        }
    }
    
    cout<<dp[1][n];  // 整个区间[1,n]合并成一堆的最小得分
    return 0;
}

图解样例

样例1: n=4, 石子=[3,2,2,3]
前缀和: a=[0,3,5,7,10]

长度2:
  dp[1][2] = 0+0+(a[2]-a[0]) = 5    （合并第1、2堆：3+2=5）
  dp[2][3] = 0+0+(a[3]-a[1]) = 4    （合并第2、3堆：2+2=4）
  dp[3][4] = 0+0+(a[4]-a[2]) = 5    （合并第3、4堆：2+3=5）

长度3:
  dp[1][3] = min(dp[1][1]+dp[2][3]+sum(1,3), dp[1][2]+dp[3][3]+sum(1,3))
           = min(0+4+7, 5+0+7) = min(11,12) = 11
  dp[2][4] = min(dp[2][2]+dp[3][4]+sum(2,4), dp[2][3]+dp[4][4]+sum(2,4))
           = min(0+5+7, 4+0+7) = min(12,11) = 11

长度4:
  dp[1][4] = min(dp[1][1]+dp[2][4]+sum(1,4),   ← 先合并[2,4]再合并[1]
                  dp[1][2]+dp[3][4]+sum(1,4),   ← 先合并[1,2]和[3,4]再合并
                  dp[1][3]+dp[4][4]+sum(1,4))   ← 先合并[1,3]再合并[4]
           = min(0+11+10, 5+5+10, 11+0+10)
           = min(21, 20, 21) = 20 ✓

最优方案：先合并(3,2)=5 → [5,2,3]
         再合并(2,3)=5 → [5,5]
         再合并(5,5)=10
         总分：5+5+10 = 20 ✓

总结

要点	说明
状态定义	dp[i][j] = 合并第 i 到 j 堆的最小得分
状态转移	dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j))
枚举顺序	区间长度从小到大
前缀和优化	sum(i,j) = a[j] - a[i-1]
初始化	dp[i][i] = 0，其余 = INF

💡 一句话

区间DP三重循环：长度 → 左端点 → 断点，转移时加区间和

---

三、「一本通 5.1 例 1」石子合并（环形区间DP）

题目

n 堆石子排成环形，每次合并相邻两堆，求最小总得分和最大总得分。

核心分析

环形和线性的区别：

• 线性：第 1 堆和第 n 堆不相邻
• 环形：第 1 堆和第 n 堆也相邻，可以合并

环形→线性的通用技巧——断环成链：

• 把数组复制一份接在后面：a[1..n] → a[1..n, 1..n]
• 这样长度 2n 的线性数组包含了所有可能的断开方式
• 在长度 n 的窗口里求区间 DP 的最值

为什么要复制？

• 环形中"断在哪里"不确定
• 复制一份后，a[i..i+n-1] 就对应从位置 i 断开的线性序列
• 对所有 i 取最值即可

同时求最大和最小：

• dp1[i][j] = 最小得分，dp2[i][j] = 最大得分
• 转移完全一样，只是 min/max 的区别

AC 代码（带详细注释）

#include<bits/stdc++.h>
#define int long long
const int INF=1e18;
using namespace std;
int n,a[510],dp1[510][510],dp2[510][510],mi1=INF,ma1;
signed main(){
    cin>>n;
    
    // dp1初始化为INF（求最小值）
    for(int i=1;i<=n*2;i++){
        for(int j=1;j<=n*2;j++){
            dp1[i][j]=INF;
        }
        // dp2默认为0（求最大值，不用初始化INF）
    }
    
    // 读入 + 断环成链：复制一份
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[n+i]=a[i];           // 复制一份接在后面
        a[i]+=a[i-1];           // 前缀和（前半段）
        dp1[i][i]=0;            // 单堆得分为0
    }
    // 后半段的前缀和继续累加
    for(int i=n+1;i<=n*2;i++){
        a[i]+=a[i-1];
        dp1[i][i]=0;
    }
    
    // 区间DP：按长度从小到大枚举
    for(int i=2;i<=n;i++){              // i = 区间长度（最大到n）
        for(int j=1;j<=2*n-i+1;j++){    // j = 左端点（范围扩大到2n）
            int ed=j+i-1;                // ed = 右端点
            for(int k=j;k<ed;k++){       // 枚举断点
                // 最小值
                dp1[j][ed]=min(dp1[j][ed],
                    dp1[j][k]+dp1[k+1][ed]+a[ed]-a[j-1]);
                // 最大值
                dp2[j][ed]=max(dp2[j][ed],
                    dp2[j][k]+dp2[k+1][ed]+a[ed]-a[j-1]);
            }
        }
    }
    
    // 在所有长度为n的窗口中取最值
    for(int i=1;i<=n;i++){
        mi1=min(mi1,dp1[i][i+n-1]);  // 从位置i开始，长度n的区间
        ma1=max(ma1,dp2[i][i+n-1]);
    }
    
    cout<<mi1<<endl<<ma1;
    return 0;
}

图解断环成链

原环形: [4, 5, 9, 4]  (n=4)

断环成链后数组: [4, 5, 9, 4, 4, 5, 9, 4]  (长度2n=8)
                 1  2  3  4  5  6  7  8

所有可能的断开方式：
  从位置1断开: 区间[1,4] = [4,5,9,4]
  从位置2断开: 区间[2,5] = [5,9,4,4]
  从位置3断开: 区间[3,6] = [9,4,4,5]
  从位置4断开: 区间[4,7] = [4,4,5,9]

对每个窗口跑区间DP，取最小/最大

样例验证

n=4, 石子=[4,5,9,4]

最优断开位置：从位置4断开 → 线性序列 [4,4,5,9]
  长度2: dp[4][5]=8, dp[5][6]=9, dp[6][7]=14
  长度3: dp[4][6]=min(0+9+13, 8+0+13)=21
         dp[5][7]=min(0+14+13, 9+0+13)=22
  长度4: dp[4][7]=min(0+22+22, 8+14+22, 21+0+22)
                     =min(44, 44, 43) = 43 ✓

最大值同理用max转移，答案=54

总结

要点	说明
环形→线性	数组复制一份，长度变 2n
区间长度	只需枚举到 n（不需要 2n）
取最值	遍历所有长度为 n 的窗口：dp[i][i+n-1]
同时求 max/min	两套 dp 数组，转移分别取 min/max

💡 一句话

环形→断环成链（复制一份），区间DP后在所有长度n窗口取最值

---

📌 今日技巧总结

技巧	适用场景	一句话
反向建图	多起点到单终点的最短路	从终点出发在反向图上跑一次Dijkstra
区间DP	相邻合并类问题	三重循环：长度→左端点→断点
前缀和优化	区间DP中快速求区间和	sum(i,j) = a[j]-a[i-1]
断环成链	环形区间DP	数组复制一份，枚举所有断开位置
朴素Dijkstra	n≤1000 的稠密图	O(n²)，每次找最小未访问点

---

🎯 复习建议：

1. 区间DP的枚举顺序是核心：必须先算短区间再算长区间
2. 环形问题先想"断环成链"，不要试图直接在环上做DP
3. 多起点最短路 = 反向建图 + 一次Dijkstra，别暴力跑多次