此题目讲的是一定的人排队买票,给出每个人买票所需要的时间,和这个人与前一个人一起买票需要的时间,求全部人买完票所需要的最小时间。
由于此题是在[kuangbin带你飞]专题上提交的,所以给出其所在的专题链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=68966#problem/H
思路:显然,此题的各种时间已经给出,则最小的时间量与其买票的人数有关,所以我们可设 dp[i] 表示以 i 为最后一个买完票所需要的最小时间量。影响 dp[i] 的值的只有两种方式,一种是 i 单独买票,此时 dp[i]=dp[i-1]+( i 单独买票的时间);另一种是 i 与前面一个一起买票,则 dp[i]=dp[i-2]+( i 与前面一个一起买票的时间)。
所以,可以得出:dp[i]=min(dp[i],dp[i-2]+d[i]); dp[i]初始化为dp[i]=dp[i-1]+s[i];
代码:
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int N,K; int dp[2010],s[2010],d[2010];//分别存储最小时间量,单独买票时间,一起买票时间 //dp[i]=min(dp[i-2]+d[i],dp[i-1]+s[i])) int main(){ cin>>N; while(N--) { cin>>K; for(int i=1;i<=K;i++) scanf("%d",&s[i]); for(int i=2;i<=K;i++) scanf("%d",&d[i]); dp[0]=0; d[1]=0; for(int i=1;i<=K;i++)//枚举终点 if(i==1){ dp[i]=s[i]; continue; } else{ dp[i]=dp[i-1]+s[i]; dp[i]=min(dp[i],dp[i-2]+d[i]); } //cout<<dp[K]<<endl; int H,M,S; H=dp[K]/3600; M=(dp[K]%3600)/60; S=dp[K]%60; H+=8; printf("%02d:%02d:%02d ",H>11?H-12:H,M,S); H>11? printf("pm\n"):printf("am\n"); //cout<<H<<" "<<M<<" "<<S<<endl; } return 0; }