HDU 1260 Tickets（簡單DP）

HDU 1260 Tickets（簡單DP）

【題意簡述】：

輸入：

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;
}