当前位置：首页 > news >正文

动态规划 dp 题目与讲解

news 2026/7/26 10:54:13

本文为在学动规的朋友们列一个题目。大家可以自己写一写，本人自己写起来觉得挺有帮助的。

[信息与未来 2026] 旅行计划

题目描述

Dr. X 想从城市000出发前往城市nnn。对于所有满足0≤i≤n−10 \le i \le n - 10≤i≤n−1的整数iii，城市iii与城市i+1i + 1i+1之间都有高铁和飞机两种出行方式：

坐高铁从城市iii到城市i+1i + 1i+1花费的时间为gig_igi；
坐飞机从城市iii到城市i+1i + 1i+1花费的时间为fif_ifi。

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

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

第三行包含nnn个空格分隔的整数f0,f1,…,fn−1f_0, f_1, \ldots, f_{n-1}f0,f1,…,fn−1，其中fif_ifi表示从城市iii坐飞机到城市i+1i + 1i+1所花费的时间。

输出格式

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

输入输出样例 #1

输入 #1

3 1 4 6 8 1 11 4

输出 #1

输入输出样例 #2

输入 #2

3 2 4 6 8 1 11 4

输出 #2

输入输出样例 #3

输入 #3

3 1 4 6 8 1 7 4

输出 #3

说明/提示

样例 1 解释

最快的方式是从城市000坐高铁到城市111，再从城市111坐高铁到城市222，最后从城市222坐飞机到城市333，总耗时为4+6+4=144 + 6 + 4 = 144+6+4=14。总共坐飞机111次，满足限制。

样例 2 解释

最快的方式是从城市000坐飞机到城市111，从城市111坐高铁到城市222，从城市222坐飞机到城市333，总耗时为1+6+4=111 + 6 + 4 = 111+6+4=11。总共坐飞机222次。

样例 3 解释

尽管g1<f1g_1 < f_1g1<f1，但在只能坐飞机111次的情况下，最优方案是从城市000直接飞到城市333，总耗时为1+7+4=121 + 7 + 4 = 121+7+4=12。

数据规模

对于10%10\%10%的数据，k=1k = 1k=1，n≤200n \le 200n≤200。
对于30%30\%30%的数据，k=1k = 1k=1，n≤100,000n \le 100,000n≤100,000。
对于另外40%40\%40%的数据，k≤100k \le 100k≤100，n≤1,000n \le 1,000n≤1,000。
对于100%100\%100%的数据，k≤1,000k \le 1,000k≤1,000，n≤100,000n \le 100,000n≤100,000，k≤nk \le nk≤n，且1≤gi,fi≤100,0001 \le g_i, f_i \le 100,0001≤gi,fi≤100,000。

大家可以自己写一写
下面给大家几个样例大家可以自己测试一下

输入：20 0
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999
输出：120

输入：20 20
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
输出：210

输入：20 1
500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500
2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1
输出：86

输入：20 5
20 100 20 100 20 100 20 100 20 100 20 100 20 100 20 100 20 100 20 100
100 1 100 2 100 3 100 4 100 5 100 6 100 7 100 8 100 9 100 10
输出：35

输入：20 3
100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
输出：20

输入：20 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
输出：20

输入：20 15
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
3 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≤j<i{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≤j<imin{dp[j][t−1]+s[i]−s[j]}

提取s[i]s[i]s[i]得：
dp[i][t]=(min⁡0≤j<i(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≤j<imin(dp[j][t−1]−s[j]))+s[i]

献代码：

#include<bits/stdc++.h>usingnamespacestd;longlongn,k;longlongg[100005],f[100005],s[100005];longlongdp[100005][1005];intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>k;for(inti=0;i<n;i++)cin>>g[i];for(inti=0;i<n;i++)cin>>f[i];// 预处理飞行前缀和 ss[0]=0;for(inti=1;i<=n;i++){s[i]=s[i-1]+f[i-1];}// 初始化，边界：t=0，0次飞机，全程高铁dp[0][0]=0;for(inti=1;i<=n;i++){dp[i][0]=dp[i-1][0]+g[i-1];}// 枚举飞机使用次数 tfor(intt=1;t<=k;t++){longlongmin_val=dp[0][t-1]-s[0];for(inti=1;i<=n;i++){// 转移1：上一个城市坐高铁过来dp[i][t]=dp[i-1][t]+g[i-1];// 转移2：从前面某个j坐飞机直达idp[i][t]=min(dp[i][t],min_val+s[i]);// 更新最小值，当前i作为后续的jlonglongnow=dp[i][t-1]-s[i];if(now<min_val)min_val=now;}}// 答案：0~k次飞机取最小longlongans=1e18;for(intt=0;t<=k;t++){ans=min(ans,dp[n][t]);}cout<<ans;return0;}