【HDOJ】1494 跑跑卡丁车

DP，将能量映射为0~14，注意当选择这圈加速的时候，这圈就不能再储存能量，同时能量14可能转化为10。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 #define MAXN 105
 9 #define MAXM 20
10 #define GATE 15
11 #define INF 0x3f3f3f3f
12 int A[MAXN];
13 int B[MAXN];
14 int dp[MAXN*MAXN][MAXM];
15 
16 int main() {
17     int l ,n;
18     int i, j, k;
19 
20 #ifndef ONLINE_JUDGE
21     freopen("data.in", "r", stdin);
22 #endif
23 
24     while (scanf("%d %d", &l, &n) != EOF) {
25         for (i=1; i<=l; ++i)
26             scanf("%d", &A[i]);
27         for (i=1; i<=l; ++i)
28             scanf("%d", &B[i]);
29         memset(dp, 0x3f, sizeof(dp));
30         /*
31         for (j=0; j<MAXM; ++j)
32             dp[0][j] = INF;
33         */
34         dp[0][0] = 0;
35         int p = 0;
36         for (k=1; k<=n; ++k) {
37             for (i=1; i<=l; ++i) {
38                 ++p;
39                 for (j=0; j<GATE; ++j) {
40                     // no speed
41                     if (j)
42                         dp[p][j] = min(dp[p][j], dp[p-1][j-1]+A[i]);
43                     // speed
44                     if (j+5<GATE)
45                         dp[p][j] = min(dp[p][j], dp[p-1][j+5]+B[i]);
46                 }
47                 // check the j=10 because, it can be turn from 14
48                 dp[p][10] = min(dp[p][10], dp[p-1][14]+A[i]);
49             }
50         }
51         int ans = INF;
52         i = l*n;
53         for (j=0; j<GATE; ++j)
54             ans = min(ans, dp[i][j]);
55         printf("%d
", ans);
56     }
57 
58     return 0;
59 }