题目地址:http://acm.swust.edu.cn/contest/0287/problem/544/
我们推测出卡丁车的氮气状态有15个(= =这个肯定你能知道 你看下面)
分别是 (我用1来代表20%)
0卡0 0卡1 0卡2 0卡3 0卡4
1卡0 1卡1 1卡2 1卡3 1卡4
2卡0 2卡1 2卡2 2卡3 2卡4
由题意: 1.前一个状态可以通过不用氮气跑一圈来使氮气增加20%到下一个状态 如0卡0 到 0卡1
2.当有卡的时候就可以使用卡来进行加速然后转换状态 如 1卡0 到 0卡0
那么我们就可以写递推式了
可以从从两个状态获取值的状态取最小值
2卡4 可以用2卡3加1转化
2卡3 可以用2卡2加1转化
2卡2 可以用2卡1加1转化
2卡1 可以用2卡0加1转化
2卡0 可以用1卡4加1转化 或者用2卡4加1转化 (题意上说了卡只能有两张)
1卡4 可以用1卡3加1转化或者用2卡4使用1卡加速转化
。。。。。。剩下的自己推一下就好了
#include <stdio.h> #include <string.h> long long int _min(long long int a,long long int b) { return a < b ? a : b; } int main() { int n, l,maps[105][2]; while (~scanf("%d %d", &l, &n)) { long long int dp[20][2] = { 0 }; for (int i = 0; i <= 20; i++) dp[i][0] = dp[i][1] = 999999;// 999999999; for (int i = 0; i < l; i++) scanf("%d",&maps[i][0]); for (int i = 0; i < l; i++) scanf("%d",&maps[i][1]); dp[0][0] = 0; int mark = 0; for (int i = 0;i < n; i++) for (int j = 0; j < l; j++) { int lmark = mark; mark = (mark + 1) % 2; dp[14][mark] = dp[13][lmark] + maps[j][0]; dp[13][mark] = dp[12][lmark] + maps[j][0]; dp[12][mark] = dp[11][lmark] + maps[j][0]; dp[11][mark] = dp[10][lmark] + maps[j][0]; dp[10][mark] = _min(dp[14][lmark],dp[9][lmark]) + maps[j][0]; for (int i = 9; i > 0; i--) dp[i][mark] = _min(dp[i+5][lmark] + maps[j][1],dp[i - 1][lmark] + maps[j][0]); dp[0][mark] = dp[5][lmark] + maps[j][1]; } long long int mi = 999999999999999; for (int i = 0; i <= 14; i++) if (dp[i][mark] < mi) mi = dp[i][mark]; printf("%lld\n",mi);
