记录82#includebits/stdc.h using namespace std; int a[210][210], dp[210]; int main(){ int n; cinn; for(int i1;in;i){//i为第几段路j为第几个站点 for(int ji1;jn;j) cin a[i][j]; }//dp[1]是0因为目的地1为出发点不花钱 for(int i2;in;i) dp[i]1e610; for(int i1;in;i){ for(int ji1; jn;j) dp[j]min(dp[j],dp[i]a[i][j]);//dp[j]是到j位置最少钱 }//dp[i]是到i最少钱,a[i][j]是在i路段选择到j的钱,i是选择的第几路段,j是其中选择的目的地 coutdp[n]; return 0; }题目传送门https://www.luogu.com.cn/problem/P1359突破口长江游艇俱乐部在长江上设置了 n 个游艇出租站 1,2,…,n。游客可在这些游艇出租站租用游艇并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 ri,j1≤ij≤n。试设计一个算法计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。思路 题目简述有n个游艇站1, 2, ..., n从上游到下游可以从任意站i直接租船到下游任意站ji j费用为r[i][j]目标从站 1 到站 n花费最少租金 注意可以中途换船比如 1→3→5总费用 r[1][3] r[3][5]这本质上是一个有向无环图DAG上的最短路径问题可用动态规划高效解决。✅ 动态规划设计状态定义dp[i]表示从站点 1 到站点 i 所需的最少租金初始状态dp[1] 0起点不花钱状态转移要到达站点j可以从任意上游站点ii j直接租船过来所以dp[j]min1≤ij(dp[i]r[i][j])答案dp[n]代码分析✅ 代码逐行解释#includebits/stdc.h using namespace std; int a[210][210], dp[210];a[i][j]存储从站i直接到站j的租金i jdp[i]从站 1 到站i的最小租金数组大小 210因n ≤ 200留余量int main(){ int n; cin n;读入站点数n 读入租金矩阵上三角for(int i 1; i n; i){ for(int j i 1; j n; j) cin a[i][j]; }输入是半矩阵只给i j的值例如n3第1行a[1][2],a[1][3]第2行a[2][3]正好对应样例输入3 5 15 → a[1][2]5, a[1][3]15 7 → a[2][3]7 初始化 DP 数组for(int i 2; i n; i) dp[i] 1e6 10;dp[1]默认为 0全局变量初始化为 0其他dp[i]设为一个足够大的数表示“暂时不可达”题目提示任何值 ≤ 1e6所以1e610是安全的上界 动态规划递推for(int i 1; i n; i){ for(int j i 1; j n; j) dp[j] min(dp[j], dp[i] a[i][j]); }外层i枚举当前出发站点内层j枚举从 i 能直达的所有下游站点更新如果通过i中转到j更便宜就更新dp[j]✅ 这正是状态转移方程的实现dp[j] min(当前dp[j], 从1到i的最小费用 i→j的直租费用) 输出答案cout dp[n]; return 0; }输出从站 1 到站 n 的最小租金 样例验证n3输入3 5 15 7即a[1][2] 5,a[1][3] 15a[2][3] 7初始化dp[1] 0dp[2] dp[3] 1000010执行循环i1:j2:dp[2] min(1000010, 05) 5j3:dp[3] min(1000010, 015) 15i2:j3:dp[3] min(15, dp[2]a[2][3]) min(15, 57) 12最终dp[3] 12✅最优路径1 → 2 → 3费用 5 7 12比直接 1→315更优✅ 总结要点说明模型DAG 最短路 / 区间 DP 变种状态dp[i] 1 到 i 的最小租金转移枚举所有可能的上一站i更新dp[j]复杂度O(n²)满足 n≤200关键技巧利用“只能往下游走”的性质按站点顺序递推此代码简洁、高效、正确解决此类“分段决策最优化”问题的标准 DP 模板