【题意简述】：
输入：
?
2 2 20 25 40 1 8输出：
?
?
这里的数据依次表示的意思为：第一个2，代表两组数据，然后下面的2表示两个人，如果单买票的话，其中第一个人会花费20S，另一个人会花费25S，如果两人一起买要花费40S（注意这里的两人一起买必须是相挨着的两个人才可以），因为题目是求得是最短的时间是多少，所以输入40S。具体的时间就是：
08:00:40 am另一个就不再赘述。
?
【分析】：对于求最短的时间，求最优解，我们可以很简单的建立状态转移方程：
dp[i] = min(dp[i-1]+ss[i], dp[i-2]+dd[i-1]) // 分别表示自己单买所花费的时间，另一个是和别人一起买所花费的时间
?
?
?
?
?
#include#include #include using namespace std; const int MAXN = 2010; int main() { int T, n; int d[MAXN], s[MAXN], dp[MAXN] = {0}; int hh, mm, ss; scanf(%d, &T); while (T--) { scanf(%d, &n); for (int i = 1; i <= n; ++i) scanf(%d, &s[i]); for (int i = 2; i <= n; ++i) scanf(%d, &d[i]); dp[1] = s[1]; for (int i = 2; i <= n; ++i) dp[i] = min(dp[i-1]+s[i], dp[i-2]+d[i]); hh = dp[n]/3600; mm = dp[n]%3600/60; ss = dp[n]%60; printf(%02d:%02d:%02d%s , (8+hh)%24, mm, ss, (hh+8)%24>12? pm: am); } return 0; }
?