Tickets

2
2
20 25
40
1
8

08:00:40 am
08:00:08 am

解题思路：

一个人能够单独买票花费一定的时间，也能够两个人一起买票，也给定一个时间。给出K个人的单独买票时间和K-1个相邻的两个人一起买票的时间。问一共花费的最小时间。

用one[i]为每一个人单独买票的时间，two[ i+1]为两个人一起买票的时间。

状态转移方程为： dp[i] = min(dp[i-1]+one[i] , dp[i-2] + two[i] )。当前第i个人分为两种情况。一是单独买，而是和前面的一块买。

另外注意最后的输出。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<cmath>

using namespace std;

const int maxn = 2000 + 50;

int n;
int k;
int dp[maxn];
int one[maxn];
int two[maxn];

int main()
{
    scanf("%d", &n);
    while( n-- )
    {
        memset(dp, 0, sizeof(dp));
        memset(one, 0, sizeof(one));
        memset(two, 0, sizeof(two));
        scanf("%d", &k);
        for(int i=1; i<=k; i++)scanf("%d", &one[i]);
        for(int i=2; i<=k; i++)scanf("%d", &two[i]);
        dp[0] = 0;dp[1] = one[1];
        for(int i=2; i<=k; i++)dp[i] = min( dp[i-1]+one[i], dp[i-2]+two[i] );
        int h = dp[k] / 3600 + 8;
        int m = dp[k] / 60 % 60;
        int s = dp[k] % 60;
        printf("%02d:%02d:%02d am\n", h, m, s);
    }

    return 0;
}