本文为在学动规的朋友们列一个题目。大家可以自己写一写本人自己写起来觉得挺有帮助的。[信息与未来 2026] 旅行计划题目描述Dr. X 想从城市000出发前往城市nnn。对于所有满足0≤i≤n−10 \le i \le n - 10≤i≤n−1的整数iii城市iii与城市i1i 1i1之间都有高铁和飞机两种出行方式坐高铁从城市iii到城市i1i 1i1花费的时间为gig_igi​坐飞机从城市iii到城市i1i 1i1花费的时间为fif_ifi​。然而Dr. X 很害怕坐飞机因此他希望整个行程中乘坐飞机的次数不得超过kkk次。为了减少坐飞机的次数Dr. X 可以选择从城市iii直接飞到城市iji jij(j≥1j \ge 1j≥1)总飞行时间等于途经各段航线的飞行时间之和fifi1⋯fij−1,\begin{aligned} f_i f_{i1} \cdots f_{ij-1}, \end{aligned}fi​fi1​⋯fij−1​,​但这样一次连续飞行只算乘坐一次飞机。请计算 Dr. X 从城市000出发到达城市nnn所需的最少时间。输入格式输入第一行包含两个整数nnn和kkk分别表示路线的数量和最多允许的坐飞机次数。第二行包含nnn个空格分隔的整数g0,g1,…,gn−1g_0, g_1, \ldots, g_{n-1}g0​,g1​,…,gn−1​其中gig_igi​表示从城市iii坐高铁到城市i1i 1i1所花费的时间。第三行包含nnn个空格分隔的整数f0,f1,…,fn−1f_0, f_1, \ldots, f_{n-1}f0​,f1​,…,fn−1​其中fif_ifi​表示从城市iii坐飞机到城市i1i 1i1所花费的时间。输出格式输出一个整数表示 Dr. X 从城市000到达城市nnn所需的最少时间。输入输出样例 #1输入 #13 1 4 6 8 1 11 4输出 #114输入输出样例 #2输入 #23 2 4 6 8 1 11 4输出 #211输入输出样例 #3输入 #33 1 4 6 8 1 7 4输出 #312说明/提示样例 1 解释最快的方式是从城市000坐高铁到城市111再从城市111坐高铁到城市222最后从城市222坐飞机到城市333总耗时为464144 6 4 1446414。总共坐飞机111次满足限制。样例 2 解释最快的方式是从城市000坐飞机到城市111从城市111坐高铁到城市222从城市222坐飞机到城市333总耗时为164111 6 4 1116411。总共坐飞机222次。样例 3 解释尽管g1f1g_1 f_1g1​f1​但在只能坐飞机111次的情况下最优方案是从城市000直接飞到城市333总耗时为174121 7 4 1217412。数据规模对于10%10\%10%的数据k1k 1k1n≤200n \le 200n≤200。对于30%30\%30%的数据k1k 1k1n≤100,000n \le 100,000n≤100,000。对于另外40%40\%40%的数据k≤100k \le 100k≤100n≤1,000n \le 1,000n≤1,000。对于100%100\%100%的数据k≤1,000k \le 1,000k≤1,000n≤100,000n \le 100,000n≤100,000k≤nk \le nk≤n且1≤gi,fi≤100,0001 \le g_i, f_i \le 100,0001≤gi​,fi​≤100,000。大家可以自己写一写下面给大家几个样例大家可以自己测试一下输入20 06 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 699999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999输出120输入20 201000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 10001 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20输出210输入20 1500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 5002 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1输出86输入20 520 100 20 100 20 100 20 100 20 100 20 100 20 100 20 100 20 100 20 100100 1 100 2 100 3 100 4 100 5 100 6 100 7 100 8 100 9 100 10输出35输入20 3100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 1000001 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1输出20输入20 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100输出20输入20 1550 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 503 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1输出72这道题用dp[t][i]\mathit{dp}[t][i]dp[t][i]表示乘坐ttt次飞机到第iii座城市所花费的最短时间。重点dp[t][i]\mathit{dp}[t][i]dp[t][i]可以分两种情况讨论1、从第i−1i-1i−1座城市到第iii座是坐高铁的那么此时到第i−1i-1i−1座城市的坐飞机次数和到第iii座城市时相等即dp[i][t]dp[i−1][t]g[i−1]\mathit{dp}[i][t] \mathit{dp}[i-1][t] g[i-1]dp[i][t]dp[i−1][t]g[i−1]2、Dr.X也有可能是从第jjj座城市连续坐飞机来第iii座城市的这次连续的飞机算一次坐飞机机会并且耗时为各航线飞行时间之和。我们为了知道第jjj座城市到第iii座城市的时间之和可以用前缀和。设s[i]s[i]s[i]第0座城市到第iii座连续坐飞机所需要的时间之和。那么第jjj座城市到第iii座城市的时间之和就是(s[i]−s[j])(s[i]-s[j])(s[i]−s[j])所以dp[i][t]min⁡0≤ji{dp[j][t−1]s[i]−s[j]}\mathit{dp}[i][t] \min_{0\le j i}\big\{ \mathit{dp}[j][t-1] s[i] - s[j] \big\}dp[i][t]0≤jimin​{dp[j][t−1]s[i]−s[j]}提取s[i]s[i]s[i]得dp[i][t](min⁡0≤ji(dp[j][t−1]−s[j]))s[i]\mathit{dp}[i][t] \bigg(\min_{0\le j i} \big(\mathit{dp}[j][t-1] - s[j]\big)\bigg) s[i]dp[i][t](0≤jimin​(dp[j][t−1]−s[j]))s[i]献代码#includebits/stdc.husingnamespacestd;longlongn,k;longlongg[100005],f[100005],s[100005];longlongdp[100005][1005];intmain(){ios::sync_with_stdio(0);cin.tie(0);cinnk;for(inti0;in;i)cing[i];for(inti0;in;i)cinf[i];// 预处理飞行前缀和 ss[0]0;for(inti1;in;i){s[i]s[i-1]f[i-1];}// 初始化边界t00次飞机全程高铁dp[0][0]0;for(inti1;in;i){dp[i][0]dp[i-1][0]g[i-1];}// 枚举飞机使用次数 tfor(intt1;tk;t){longlongmin_valdp[0][t-1]-s[0];for(inti1;in;i){// 转移1上一个城市坐高铁过来dp[i][t]dp[i-1][t]g[i-1];// 转移2从前面某个j坐飞机直达idp[i][t]min(dp[i][t],min_vals[i]);// 更新最小值当前i作为后续的jlonglongnowdp[i][t-1]-s[i];if(nowmin_val)min_valnow;}}// 答案0~k次飞机取最小longlongans1e18;for(intt0;tk;t){ansmin(ans,dp[n][t]);}coutans;return0;}若代码有何不妥之处请大佬们在评论区指点。感谢大家的浏览