FJNU第二十届低年级程序设计竞赛(正式赛)-ProblemC-汪老司机（简单DP）

问题 C: 汪老司机

时间限制: 1 Sec  内存限制:128 MB

题目描述

汪老司机是实验室出了名的老司机，早在大一就拿到了驾照，每年的暑假他都会带家人开车出游，今年的暑假也不例外，汪老司机今年准备带家人去平潭游玩，汪老司机的家离平潭有两条路，每条路都存在n个路段，两条路的n个路段长度都相同，两条路的每个路段都分别存在一个耗油量ai和bi（走完第i个路段，两条路分别耗油ai和bi），因为汪老司机是个熟练的老司机，因此他可以在任意一条路上变道到另外一条路上（只允许在路段的端点变道），虽然是老司机但是他也不能变道超过k次，因为这样容易被警察发现，汪老司机想知道他最少需要耗费多少油才能到达平潭。 注意：当汪老司机在家时，他可以选择两条路的任意一条路作为起点但不消耗他的变道次数

输入

包含多组样例，第一行一个数字T，表示样例的个数 对于每组样例： 第一行两个个数字n，k，分别表示道路路段的个数和能够变道的最多次数 第二行n个数字ai表示第一条道路不同路段的耗油量 第三行n个数字bi表示第二条道路不同路段的耗油量 ( T <= 25, 1 <= n <= 10000, 0 <= k <= 10, 0 <= ai <= 1e9, 0 <= bi <= 1e9 )

输出

对于每组样例输出一行一个数字，表示最少的耗费量

样例输入

1

6 5

1 4 5 8 9 12

2 3 6 7 10 11

样例输出

36

提示

汪老司机行走的路线：a1 -> b2 -> a3 -> b4 -> a5 -> b6

思路：简单DP。 Word is too cold，show  you  my code。

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <iostream> // C++头文件，C++完全兼容C #include <algorithm> // C++头文件，C++完全兼容C #define fre freopen("in.txt","r",stdin) //以文件代替控制台输入，比赛时很常用，能缩短输入测试样例的时间 #define INF 0x3f3f3f3f #define inf 1e60 using namespace std; // C++头文件，C++完全兼容C #define N 10005 // 宏定义 #define LL long long //宏定义 LL dp[N][2][15]; //第一个[]表示走到第几格，第二个[]表示第几行（0 或 1），第三个[]表示已经进行了几次换道 //其实第一个[]完全可以省略，因为进行操作的都是当前路段和前1个路段 int a[N],b[N]; //记录每条道的值 int main(){ //fre; int t; scanf("%d",&t); //测试样例数 while(t--){ int n,k; scanf("%d%d",&n,&k); memset(dp,INF,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); dp[0][0][0] = dp[0][1][0] = dp[0][0][1] = dp[0][1][1] = 0; //一开始第0段路置为0 for(int i=1; i<=n; i++){ int top = min(k-1,i-1); //需要进行动态规划的变道次数 dp[i][0][0] = dp[i-1][0][0] + a[i]; //第0条路，从未变道 dp[i][1][0] = dp[i-1][1][0] + b[i]; //第1条路，从未变道 for(int j=0; j<=top; j++){ dp[i][0][j+1] = min(dp[i-1][0][j+1] + a[i], dp[i-1][1][j] + a[i]); //见图片解析 dp[i][1][j+1] = min(dp[i-1][1][j+1] + b[i], dp[i-1][0][j] + b[i]); //见图片解析 } } LL ans = inf; for(int i=0;i<=k;i++){ //最后将第n段路的所有状态取最小值 ans = min(ans, dp[n][0][i]); ans = min(ans, dp[n][1][i]); } printf("%lld\n",ans); } }