Tickets HDU

题目大意：n个人要买东西，然后每个人可以选择自己购买，花费的时间是ai，也可以选择和自己前边的人一块购买这两个人一块买花费的时间是bi，问这n个人需要的最少时间，如果从08:00:00开始算起，那么最早几点结束。

题解：定义状态dp[i]表示前i个人的需要的最少时间，第i个人可以自己买dp[i]=dp[i-1]+ai，也可以和前边的人一块买,dp[i]=dp[i-2]+bi，然后取最小值就好了。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=2000+7;
int arr1[N];
int arr2[N];
int dp[N]; 
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr1[i];
    for(int i=2;i<=n;i++) cin>>arr2[i];
    dp[1]=arr1[1];
    dp[2]=min(arr2[2],arr1[1]+arr1[2]);
    for(int i=3;i<=n;i++) dp[i]=min(dp[i-1]+arr1[i],dp[i-2]+arr2[i]);
    int sec=dp[n]%60;
    dp[n]-=sec;
    int cnt=dp[n]/60;
    int minute=cnt%60;
    cnt-=minute;
    int h=cnt/60;
    h+=8; 
    if(h<10) printf("0%d",h);
    else printf("%d",h);
    printf(":");
    if(minute<10)  printf("0%d",minute);
    else printf("%d",minute);
    printf(":");
    if(sec<10) printf("0%d",sec);
    else printf("%d",sec);
    if(h<12) printf(" am
");
    else printf(" pm
");
} 
int main(){
    int t;
    scanf("%d",&t);
    while(t--) solve();
    return 0;
}