首页 > 代码库 > HDU 1494 跑跑卡丁车

HDU 1494 跑跑卡丁车

很无爱的一道题。

题解都看得一知半解的。

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int maxn = 10000 + 10; 9 const int INF = 0xffffff0;10 int dp[maxn][16];11 int a[maxn], b[maxn];12 13 int main(void)14 {15     #ifdef LOCAL16         freopen("1494in.txt", "r", stdin);17     #endif18 19     int L, N;20     while(scanf("%d%d", &L, &N) == 2)21     {22         int tot = L * N;23         int i;24         for(i = 0; i < L; ++i)25             scanf("%d", &a[i]);26         for(i = 0; i < L; ++i)27             scanf("%d", &b[i]);28         for(i = L; i < tot; ++i)29         {30             a[i] = a[i % L];31             b[i] = b[i % L];32         }33 34         for(i = 0; i <= tot; ++i)35             for(int j = 0; j <= 15; ++j)36                 dp[i][j] = INF;37         dp[1][1] = a[0];38 39         for(i = 1; i < tot; ++i)40             for(int j = 0; j < 15; ++j)41             {42                 int k = j + 1;43                 if(k == 15)44                     k = 10;45                 dp[i+1][k] = min(dp[i][j] + a[i], dp[i+1][k]);46                 if(j >= 5)47                     dp[i+1][j-5] = min(dp[i][j] + b[i], dp[i+1][j-5]);48             }49 50         int ans = INF;51         for(i = 0; i < 15; ++i)52             ans = min(ans, dp[tot][i]);53         printf("%d\n", ans);54     }55     56     return 0;57 }
代码君