HDU – 1260 Tickets

HDU 1260

又是一道简单DP…
轮到第i个人的时候,要么是单独一人买,要么是和前面一个人组团买.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

int n;
int k;
int a[2005];
int b[2005];
int f[2005];
int main() {
  cin>>n;
  while(n--){
    cin>>k;
    for(int i=1;i<=k;++i){
      cin>>a[i];
    }
    for(int i=1;i<=k-1;++i){
      cin>>b[i];
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=k;++i){
      f[i]=min(f[i],f[i-1]+a[i]);
      if(i>=2) f[i]=min(f[i],f[i-2]+b[i-1]);
    }
    int s=f[k]%60;
    int m=f[k]/60%60;
    int h=f[k]/60/60;
    char state[]="am";
    if(8+h>12) state[0]='a',h-=12;
    printf("%02d:%02d:%02d %s\n",8+h,m,s,state);
  }
  return 0;
}