题目链接
中文题，题意一目了然
L段路，N圈
那么可以视为L*N段路 跑一圈所用最快时间。
每个加速卡由100能量得到，每跑一段路得到20的能量，最多获得2张加速卡以及80能量。
可以简化成 1表示20能量，则5表示一张加速卡，10表示两张，14表示2张加速卡以及80能量，当为15时则成了两张加速卡以及0能量
设dp[i][j]为在第i段路，能量为j时所用最快时间，则状态转移方程则为：
dp[i 1][10] = min(dp[i][j] a[i], dp[i 1][10]) , j 1 == 15
dp[i 1][j 1] = min(dp[i][j] a[i], dp[i 1][j 1]) , j 1 < 15
dp[i 1][j-5] = min(dp[i][j] b[i], dp[i 1][j-5]) , j 1 >= 5
最终的答案便是在dp[L*N][]中寻找最小值
代码如下：
代码语言：javascript复制 1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #include <cmath>
5 #include <iostream>
6 #include <map>
7 #include <list>
8 #include <queue>
9 #include <stack>
10 #include <string>
11 #include <algorithm>
12 #include <iterator>
13 using namespace std;
14 #define MAXN 10010
15 #define INF 0x3f3f3f3f
16 #define MOD 1000000007
17 #define eps 1e-6
18 #define LL long long
19 int dp[MAXN][20] , a[MAXN] , b[MAXN];
20 int l , n;
21 void read()
22 {
23 for(int i = 1; i <= l; i )
24 {
25 scanf("%d",&a[i]);
26 for(int j = 1; (l * j i) <= l*n; j )
27 a[l * j i] = a[i];
28 }
29 for(int i = 1; i <= l; i )
30 {
31 scanf("%d",&b[i]);
32 for(int j = 1; (l * j i) <= l*n; j )
33 b[l * j i] = b[i];
34 }
35 }
36 void solve()
37 {
38 /*
39 * dp[i 1][j 1] = min(dp[i][j] a[i] , dp[i 1][j 1]);
40 * dp[i][j-5] = min(dp[i-1][j] b[i] , dp[i][j-5]);
41 */
42 int cnt = l * n;
43 memset(dp , 0x3f , sizeof(dp));
44 dp[1][1] = a[1];
45 for(int i = 1; i < cnt; i )
46 {
47 for(int j = 0; j < 15; j )
48 {
49 if(j 1 == 15) dp[i 1][10] = min(dp[i][j] a[i 1] , dp[i 1][10]);
50 if(j 1 < 15) dp[i 1][j 1] = min(dp[i][j] a[i 1] , dp[i 1][j 1]);
51 if(j >= 5) dp[i 1][j-5] = min(dp[i][j] b[i 1] , dp[i 1][j-5]);
52 }
53 }
54 int ans = INF;
55 for(int i = 0; i < 15; i )
56 ans = min(ans , dp[cnt][i]);
57 printf("%dn",ans);
58 }
59
60 int main()
61 {
62 while(scanf("%d %d",&l,&n) != EOF)
63 {
64 read();
65 solve();
66 }
67 return 0;
68 }
