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 + 1i+1之间都有高铁和飞机两种出行方式：

• 坐高铁从城市i ii到城市i + 1 i + 1i+1花费的时间为g i g_igi​；
• 坐飞机从城市i ii到城市i + 1 i + 1i+1花费的时间为f i f_ifi​。

然而，Dr. X 很害怕坐飞机，因此他希望整个行程中乘坐飞机的次数不得超过k kk次。

为了减少坐飞机的次数，Dr. X 可以选择从城市i ii直接飞到城市i + j i + ji+j(j ≥ 1 j \ge 1j≥1)，总飞行时间等于途经各段航线的飞行时间之和f i + f i + 1 + ⋯ + f i + j − 1 , \begin{aligned} f_i + f_{i+1} + \cdots + f_{i+j-1}, \end{aligned}fi​+fi+1​+⋯+fi+j−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 + 1i+1所花费的时间。

第三行包含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 + 1i+1所花费的时间。

输出格式

输出一个整数，表示 Dr. X 从城市0 00到达城市n nn所需的最少时间。

输入输出样例 1

输入 1

3 1 4 6 8 1 11 4

输出 1

14

输入输出样例 2

输入 2

3 2 4 6 8 1 11 4

输出 2

11

输入输出样例 3

输入 3

3 1 4 6 8 1 7 4

输出 3

12

说明/提示

样例 1 解释

• 最快的方式是从城市0 00坐高铁到城市1 11，再从城市1 11坐高铁到城市2 22，最后从城市2 22坐飞机到城市3 33，总耗时为4 + 6 + 4 = 14 4 + 6 + 4 = 144+6+4=14。总共坐飞机1 11次，满足限制。

样例 2 解释

• 最快的方式是从城市0 00坐飞机到城市1 11，从城市1 11坐高铁到城市2 22，从城市2 22坐飞机到城市3 33，总耗时为1 + 6 + 4 = 11 1 + 6 + 4 = 111+6+4=11。总共坐飞机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 = 121+7+4=12。

数据规模

• 对于10 % 10\%10%的数据，k = 1 k = 1k=1，n ≤ 200 n \le 200n≤200。
• 对于30 % 30\%30%的数据，k = 1 k = 1k=1，n ≤ 100 , 000 n \le 100,000n≤100,000。
• 对于另外40 % 40\%40%的数据，k ≤ 100 k \le 100k≤100，n ≤ 1 , 000 n \le 1,000n≤1,000。
• 对于100 % 100\%100%的数据，k ≤ 1 , 000 k \le 1,000k≤1,000，n ≤ 100 , 000 n \le 100,000n≤100,000，k ≤ 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_s+f_{s+1}+\cdots+f_{i-1}fs​+fs+1​+⋯+fi−1​

用前缀和s u m F [ i ] = ∑ p = 0 i − 1 f p sumF[i]=\sum_{p=0}^{i-1}f_psumF[i]=∑p=0i−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 次飞机块后的最短时间。

转移分三种情况：

1. 不使用这次新增的飞机次数：c [ i ] = p [ i ] c[i]=p[i]c[i]=p[i]
2. 最后一段坐高铁：c [ i ] = c [ i − 1 ] + g i − 1 c[i]=c[i-1]+g_{i-1}c[i]=c[i−1]+gi−1​
3. 最后一个飞机块从某个 (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_{s<i}\{p[s]+sumF[i]-sumF[s]\} =sumF[i]+\min_{s<i}\{p[s]-sumF[s]\}c[i]=mins<i​{p[s]+sumF[i]−sumF[s]}=sumF[i]+mins<i​{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)，可以通过本题。

---

代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,k;cin>>n>>k;vector<int>g(n);for(inti=0;i<n;i++)cin>>g[i];vector<longlong>s(n+1,0);for(inti=0;i<n;i++){longlongx;cin>>x;s[i+1]=s[i]+x;}vector<longlong>p(n+1),c(n+1);p[0]=0;for(inti=1;i<=n;i++)p[i]=p[i-1]+g[i-1];//0次飞机只能坐高铁for(intt=1;t<=k;t++){c[0]=0;//起点到城市0时间为0longlongm=0;//s=0时p[0]-s[0]=0for(inti=1;i<=n;i++){c[i]=p[i];//不使用这次新增的飞机次数longlongv=s[i]+m;//从某个起点坐一个飞机块到iif(v<c[i])c[i]=v;v=c[i-1]+g[i-1];//最后一段坐高铁if(v<c[i])c[i]=v;longlongw=p[i]-s[i];//把i作为以后飞机块的起点if(w<m)m=w;}swap(p,c);}cout<<p[n];return0;}

---

功能分析

1. 读入 n,k 和高铁时间数组 g。
2. 读入飞机时间的同时，直接计算出飞行时间前缀和 s，方便快速求任意连续飞行区间的总时间。
3. 初始化 p：一次飞机都不坐时，只能全程坐高铁。
4. 外层循环枚举“允许使用的飞机块数量”从 1 到 k。
5. 内层从左到右更新每个城市：
   • 继承上一轮答案；
   • 用维护的min ⁡ ( p [ s ] − s [ s ] ) \min(p[s]-s[s])min(p[s]−s[s])完成一次飞机块转移；
   • 用当前城市坐高铁转移。
6. 使用滚动数组p和c交换，减少空间。
7. 最终输出 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++标准模板库STL：
https://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 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}