HDU 1260 Tickets

题意：有N个人要买票，你可以一个一个人卖票，时间分别为Xs，也可以相邻两个人一起卖票，时间为Ys，从早上八点开始卖票，问你何时最早将N个人的票卖完。

思路：解决情况是当前最优，要么就单卖，状态最优就是前一个人的，要么和前一个人一起拼凑，状态最优是前两个人的，取时间最短的。

时间显示问题，注意下上下午的事情就好了。

dp[i] = min(dp[i-1]+signal[i],dp[i-2]+unit[i])

/**

Sample Input

2

2

20 25

40

1

8

Sample Output

08:00:40 am

08:00:08 am

**/

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 2005;

int signal[maxn];

int unit[maxn];

int H,M,S;

int dp[maxn];

char t[5];

void conver(int time){

    H = (time/3600+H)%24;

    M = (time/60)%60;

    S = (time)%60;

    if(H > 12){

        strcpy(t,"pm");

    }

    H = H%12;

}

int main()

{

    int N,K;

    scanf("%d",&N);

    while(N--){

        memset(dp,0,sizeof(dp));

        H = 8;

        M = S = 0;

        strcpy(t,"am");

        scanf("%d",&K);

        for(int i=0;i<K;i++){

            scanf("%d",&signal[i]);

        }

        for(int i=1;i<K;i++){

            scanf("%d",&unit[i]);

        }

        dp[0] = signal[0]; //注意对第一个人的初始化

        for(int i=1;i<K;i++){

            dp[i] = min(dp[i-1]+signal[i],dp[i-2]+unit[i]);

        }

        conver(dp[K-1]);

        printf("%02d:%02d:%02d %s\n",H,M,S,t);

    }

    return 0;

}