又是一道简单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;
}