HDU1260 Tickets

题意：有n组数据，每组数据输入k，表示要买k张票，然后输入k个数字，表示单买每一张票的价格，然后输入k-1个数，表示相邻两个一起买的价格。

分析：dp[i]表示买前i张票的最少钱数，可以推导出dp[i] = min(dp[i-2]+p[i,i-1], dp[i-1]+p[i] );

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

const int oo = 1e9;

int a[2005], b[2005];
int dp[2005];

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


    return 0;
}