Hdu 1494 跑跑卡丁车

 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("%d\n",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 }