【題目敘述】https://vjudge.net/problem/HDU-1260
【解題想法】DP 遞推
- 有 K 位客人(1 ~ K)。
- a[ ]：單人買票花費的時間, a[0] = 0。
- b[ ]：相鄰兩人一起買票的時間，b[0] = b[1] = 0。
- dp[i]：服務到第 i 個人時，累計花費的最短時間。初始值INF，dp[1] = a[1]。
- 狀態轉移方程：
- dp[i] = min(dp[i-1] + a[i], dp[i-2] + b[i]);
- 注意列印格式，”am|pm” 位小寫。
- 用printf( )列印 C++字串：透過 str.c_str() 轉換。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define INF 0x3F3F3F3F
int N, K;
int a[2005], b[2005], dp[2005];
void printTime(int t){
int hour = t / 3600;
int min = (t - hour * 3600) / 60;
int sec = t - hour * 3600 - min * 60;
hour += 8;
string flag;
if (hour > 12){
hour -= 12;
flag = "pm";
} else {
flag = "am";
}
printf("%02d:%02d:%02d %s\n", hour, min, sec, flag.c_str());
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
while (N--){
cin >> K;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
b[1] = INF;
for (int i=1; i<=K; i++){
cin >> a[i];
}
for (int i=2; i<=K; i++){
cin >> b[i];
}
memset(dp, 0x3F, sizeof(dp));
dp[1] = a[1];
for (int i=2; i<=K; i++){
if (i == 2){
dp[i] = min(dp[i-1] + a[i], b[i]);
} else {
dp[i] = min(dp[i-1] + a[i], dp[i-2] + b[i]);
}
}
printTime(dp[K]);
}
return 0;
}