题目大意：给出 N 组测试样例，每组样例第一行表示 k 个人，第二行表示每个人购票所花时间，第三行 k-1 个数表示相邻两人一起购票需要的时间。8 点上班，问几点能下班。 解题思路：对于每个人，都有自己买 s[i] 或者是和前一个人一起买（除第一个人外）d[i] 两种方式。dp 记录当前人购票时花费最少时间，状态转移方程dp[i] = min(dp[i-1]+s[i], dp[i-2]+d[i])，总花费时间转换一下输出下班时间
#include<iostream> #include<stdio.h> #include<algorithm> #include<cmath> #include<string.h> #include<string> #include<queue> #include<map> #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) const int INF = 0x3f3f3f3f; const int NINF = -INF -1; const int MAXN = 2000+5; using namespace std; int n, k; int s[MAXN], d[MAXN]; int dp[MAXN]; int hh, mm, ss; int main() { scanf("%d", &n); while (n--) { scanf("%d", &k); for (int i = 0; i < k; i++) s[i] = d[i] = dp[i] = INF; for (int i = 0; i < k; i++) scanf("%d", &s[i]); for (int i = 1; i < k; i++) scanf("%d", &d[i]); dp[0] = s[0]; dp[1] = min(dp[0]+s[1], d[1]); for (int i = 2; i < k; i++) dp[i] = min(dp[i-1]+s[i], dp[i-2]+d[i]); hh = 8+dp[k-1]/3600; mm = dp[k-1]%3600/60; ss = dp[k-1]%60; printf("d:d:d ", hh, mm, ss); if (hh > 12) printf("pm\n"); else printf("am\n"); } return 0; }