2026年【江苏“信息与未来”编程思维】真题及题解（T5：旅行计划）

2026年【江苏“信息与未来”编程思维】真题及题解T5旅行计划题目描述Dr. X 想从城市0 00出发前往城市n nn。对于所有满足0 ≤ i ≤ n − 1 0 \le i \le n - 10≤i≤n−1的整数i ii城市i ii与城市i 1 i 1i1之间都有高铁和飞机两种出行方式坐高铁从城市i ii到城市i 1 i 1i1花费的时间为g i g_igi​坐飞机从城市i ii到城市i 1 i 1i1花费的时间为f i f_ifi​。然而Dr. X 很害怕坐飞机因此他希望整个行程中乘坐飞机的次数不得超过k kk次。为了减少坐飞机的次数Dr. X 可以选择从城市i ii直接飞到城市i j i jij(j ≥ 1 j \ge 1j≥1)总飞行时间等于途经各段航线的飞行时间之和f i f i 1 ⋯ f i j − 1 , \begin{aligned} f_i f_{i1} \cdots f_{ij-1}, \end{aligned}fi​fi1​⋯fij−1​,​但这样一次连续飞行只算乘坐一次飞机。请计算 Dr. X 从城市0 00出发到达城市n nn所需的最少时间。输入格式输入第一行包含两个整数n nn和k kk分别表示路线的数量和最多允许的坐飞机次数。第二行包含n nn个空格分隔的整数g 0 , g 1 , … , g n − 1 g_0, g_1, \ldots, g_{n-1}g0​,g1​,…,gn−1​其中g i g_igi​表示从城市i ii坐高铁到城市i 1 i 1i1所花费的时间。第三行包含n nn个空格分隔的整数f 0 , f 1 , … , f n − 1 f_0, f_1, \ldots, f_{n-1}f0​,f1​,…,fn−1​其中f i f_ifi​表示从城市i ii坐飞机到城市i 1 i 1i1所花费的时间。输出格式输出一个整数表示 Dr. X 从城市0 00到达城市n nn所需的最少时间。输入输出样例 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 解释最快的方式是从城市0 00坐高铁到城市1 11再从城市1 11坐高铁到城市2 22最后从城市2 22坐飞机到城市3 33总耗时为4 6 4 14 4 6 4 1446414。总共坐飞机1 11次满足限制。样例 2 解释最快的方式是从城市0 00坐飞机到城市1 11从城市1 11坐高铁到城市2 22从城市2 22坐飞机到城市3 33总耗时为1 6 4 11 1 6 4 1116411。总共坐飞机2 22次。样例 3 解释尽管g 1 f 1 g_1 f_1g1​f1​但在只能坐飞机1 11次的情况下最优方案是从城市0 00直接飞到城市3 33总耗时为1 7 4 12 1 7 4 1217412。数据规模对于10 % 10\%10%的数据k 1 k 1k1n ≤ 200 n \le 200n≤200。对于30 % 30\%30%的数据k 1 k 1k1n ≤ 100 , 000 n \le 100,000n≤100,000。对于另外40 % 40\%40%的数据k ≤ 100 k \le 100k≤100n ≤ 1 , 000 n \le 1,000n≤1,000。对于100 % 100\%100%的数据k ≤ 1 , 000 k \le 1,000k≤1,000n ≤ 100 , 000 n \le 100,000n≤100,000k ≤ n k \le nk≤n且1 ≤ g i , f i ≤ 100 , 000 1 \le g_i, f_i \le 100,0001≤gi​,fi​≤100,000。思路分析把“连续坐飞机经过若干段”看成一个飞机块例如从城市 s 飞到城市 i中间不换高铁只算坐 1 次飞机花费为f s f s 1 ⋯ f i − 1 f_sf_{s1}\cdotsf_{i-1}fs​fs1​⋯fi−1​用前缀和s u m F [ i ] ∑ p 0 i − 1 f p sumF[i]\sum_{p0}^{i-1}f_psumF[i]∑p0i−1​fp​可以快速表示成s u m F [ i ] − s u m F [ s ] sumF[i]-sumF[s]sumF[i]−sumF[s]。定义p[i]上一轮 DP 值表示使用不超过某个次数时到城市 (i) 的最短时间。c[i]当前轮 DP 值表示多允许 1 次飞机块后的最短时间。转移分三种情况不使用这次新增的飞机次数c [ i ] p [ i ] c[i]p[i]c[i]p[i]最后一段坐高铁c [ i ] c [ i − 1 ] g i − 1 c[i]c[i-1]g_{i-1}c[i]c[i−1]gi−1​最后一个飞机块从某个 (s) 飞到 (i)c [ i ] min ⁡ s i { p [ s ] s u m F [ i ] − s u m F [ s ] } s u m F [ i ] min ⁡ s i { p [ s ] − s u m F [ s ] } c[i]\min_{si}\{p[s]sumF[i]-sumF[s]\} sumF[i]\min_{si}\{p[s]-sumF[s]\}c[i]minsi​{p[s]sumF[i]−sumF[s]}sumF[i]minsi​{p[s]−sumF[s]}从左到右扫描时维护min ⁡ { p [ s ] − s u m F [ s ] } \min\{p[s]-sumF[s]\}min{p[s]−sumF[s]}所以每个城市转移是 O(1)。总时间复杂度 O(kn)空间复杂度 O(n)可以通过本题。代码实现#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,k;cinnk;vectorintg(n);for(inti0;in;i)cing[i];vectorlonglongs(n1,0);for(inti0;in;i){longlongx;cinx;s[i1]s[i]x;}vectorlonglongp(n1),c(n1);p[0]0;for(inti1;in;i)p[i]p[i-1]g[i-1];//0次飞机只能坐高铁for(intt1;tk;t){c[0]0;//起点到城市0时间为0longlongm0;//s0时p[0]-s[0]0for(inti1;in;i){c[i]p[i];//不使用这次新增的飞机次数longlongvs[i]m;//从某个起点坐一个飞机块到iif(vc[i])c[i]v;vc[i-1]g[i-1];//最后一段坐高铁if(vc[i])c[i]v;longlongwp[i]-s[i];//把i作为以后飞机块的起点if(wm)mw;}swap(p,c);}coutp[n];return0;}功能分析读入 n,k 和高铁时间数组 g。读入飞机时间的同时直接计算出飞行时间前缀和 s方便快速求任意连续飞行区间的总时间。初始化 p一次飞机都不坐时只能全程坐高铁。外层循环枚举“允许使用的飞机块数量”从 1 到 k。内层从左到右更新每个城市继承上一轮答案用维护的min ⁡ ( p [ s ] − s [ s ] ) \min(p[s]-s[s])min(p[s]−s[s])完成一次飞机块转移用当前城市坐高铁转移。使用滚动数组p和c交换减少空间。最终输出 p[n]即最多坐 k 次飞机时的最短时间。更多内容请关注专栏信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}