HDU 1260 Tickets

题目链接: [kuangbin带你飞]专题十二 基础DP1 H - Tickets

题意

给出T,表示有T组样例
给出n,表示有n个人买票
给出n个数表示这个人单独买票会花的时间..
给出n-1个数,表示这个人和前面那个人一起买票会花的时间
求最快多少分钟可以把票买完

思路

dp[i] = max(dp[i-1]+a[i], dp[i-2]+b[i])

代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

const int N = 2006;
int dp[N], a[N], b[N];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
            scanf("%d", &a[i]);
        for(int i=2; i<=n; i++)
            scanf("%d", &b[i]);
        dp[1] = a[1];
        for(int i=2; i<=n; i++)
        {
            dp[i] = min(dp[i-1]+a[i], dp[i-2]+b[i]);
        }
        int s = dp[n]%60;
        int m = dp[n]/60%60;
        int h = (dp[n]/3600 + 8)%24;
        if(h > 12)
            printf("%02d:%02d:%02d pm\n", h-12, m, s);
        else
            printf("%02d:%02d:%02d am\n", h, m, s);
    }
    return 0;
}