题意
k个人买票 每个人有自己买票的时长，任意两个相邻的人有一块买票的时长 问最短耗时
题解
。。基本DP
dp[i]=min(dp[i-1]+si[i],dp[i-2]+adi[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<cstdio>
#include<algorithm>
using namespace std;
int dp[2020],adi[2020],si[2020];
int main(){
int T;
scanf("%d",&T);
while(T--){
int k;
scanf("%d",&k);
for(int i=1;i<=k;++i){
scanf("%d",&si[i]);
}
for(int i=2;i<=k;++i){
scanf("%d",&adi[i]);
}
dp[0]=0;
dp[1]=si[1];
for(int i=2;i<=k;++i){
dp[i]=min(dp[i-1]+si[i],dp[i-2]+adi[i]);
}
int s=dp[k]%60,m=(dp[k]/60)%60,h=(dp[k]/3600+8)%24;
int af=0;
if(h>12){
af=1;
h-=12;
}
printf("%02d:%02d:%02d %s\n",h,m,s,af?"pm":"am");
}
return 0;
}
|