题意:中文题、、、
思路:技能槽的状态一共有15种状态0% 20% 40% 60% 80% 100% 120%.....
dp[i][j] 代表通过第i条路的技能槽状态是j , 所以要考虑好哪些状态可以到达dp[i][j]是最优的就行了
dp[i][j] = min(dp[i-1][j-1] + a[i] , dp[i-1][j+5] + b[i]) . 然后就是处理细节
1.N圈处理 只要a[i%L] 就行
2.状态j == 10 时 的 上一步状态也可能是 状态14
#include<iostream> #include<cstdio> #include<cstring> #define inf 1000000 using namespace std; int Min(int a , int b) { return a < b ? a : b; } int main() { int dp[10010][16]; int a[110] , b[110] , L , N , i , j; while(~scanf("%d%d",&L,&N)) { for(i = 0; i < L ; i ++) scanf("%d",&a[i]); for(i = 0; i < L ; i ++) scanf("%d",&b[i]); for(i = 0; i < L*N ; i ++) for(j = 0; j < 15 ; j ++) dp[i][j] = inf; dp[0][1] = a[0]; for(i = 1 ; i < L*N ; i ++) { for(j = 0 ; j <= 14 ; j ++) { if(j >= 10) dp[i][j] = Min(dp[i][j] , dp[i-1][j-1]+a[i%L]); if(j < 10) { if(j!=0) dp[i][j] = Min(dp[i-1][j-1]+a[i%L] , dp[i-1][j+5]+b[i%L]); else dp[i][j] = Min(dp[i][j] , dp[i-1][j+5] + b[i%L]); } if(j == 10) dp[i][j] = Min(dp[i-1][j-1]+a[i%L] , dp[i-1][14]+a[i%L]); //printf("%d\n",dp[i][j]); } //printf("**************\n"); } int maxx = inf; for(j = 0 ; j < 15 ; j ++) { if(dp[L*N-1][j] < maxx) maxx = dp[L*N-1][j]; } printf("%d\n",maxx); } }