中文题,题意略,DP。
由于赛道分为L段,所以很容易想到让DP的第一维用来表示当前在第几段赛道。
因为加速卡要100%能量才会获得一张,而每走一段赛道又会获得20%的能量,所以我们可以把能量槽也分成段,具有5段能量槽就可以获得一张加速卡
那么用第二维来表示当前的能量槽的段数话,就可以表示出所有的状态了。
dp[i][j]表示在第i段赛道具有j段能量槽所花费的最短时间。
这样就可以得到状态转移方程
dp[i][j] = min(dp[i][j], min(dp[i-1][j-1] + a[i], dp[i-1][j+5] + b[i]))
这个题还有一个trick,就是当你已经有了2张加速卡(10段能量后)即使你又获得了5段能量,依然只能有两张加速卡
所以当j == 10时 dp[i][j] 还可能从dp[i-1][14]推出。
最后关于N圈的处理,求余或者拼起来均可……
View Code
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define INF 0x73737373 7 int a[10010], b[10010], dp[10010][15]; 8 void input(int L, int N, int a[]) 9 { 10 for(int i = 1; i <= L; i++) 11 { 12 scanf("%d", &a[i]); 13 for(int j = 1; j < N; j++) 14 a[i + j * L] = a[i]; 15 } 16 } 17 int main() 18 { 19 int L, N; 20 while(~scanf("%d%d", &L, &N)) 21 { 22 input(L, N, a); 23 input(L, N, b); 24 for(int i = 0; i <= L * N; i++) 25 for(int j = 0; j < 15; j++) 26 dp[i][j] = INF; 27 dp[0][0] = 0; 28 for(int i = 1; i <= L * N; i++) 29 { 30 for(int j = 0; j < 15; j++) 31 { 32 if(j != 0)dp[i][j] = min(dp[i][j], dp[i-1][j-1] + a[i]); 33 if(j == 10) dp[i][j] = min(dp[i][j], dp[i-1][14] + a[i]); 34 if(j < 10)dp[i][j] = min(dp[i][j], dp[i-1][j+5] + b[i]); 35 } 36 } 37 int ret = INF; 38 for(int i = 0; i < 15; i++) 39 ret = min(dp[L * N][i], ret); 40 printf("%d\n", ret); 41 } 42 return 0; 43 }