Tickets hdu 1206

题源：Tickets hdu 1206
题目：
现在有n个人要买电影票，如果知道每个人单独买票花费的时间，还有和前一个人一起买花费的时间，问最少花多长时间可以全部买完票。
Input
　　　　给出 N(1<=N<=10)，表示有N组样例 　　　　给出K (1<=K<=2000)，表示有K个人买票… 　　　　给出K个数表示这个人单独买票会花的时间…保证每个数 (0s<=Si<=25s) 　　　　给出K-1个数，表示这个人和前面那个人一起买票会花的时间…保证每个数 (0s<=Si<=50s)
Output
对于每一组数据，你需要给出电影院售票结束的时间，售票开始的时间为 08:00:00 am. 时间格式为： HH:MM:SS am|pm. 具体看样例输出
Sample Input
2
2
20 25
40
1
8
Sample Output
08:00:40 am
08:00:08 am

**思路：**这道题我明明知道他是dp，而我却不会；
其实就是设一个dp数组，然后记录买每张票花费时间的最小值；
如果到买第i张票的时候，两个人分开买时间最少 则 :dp[i]=dp[i-1]+a[i],dp[i-1]为买到上一张票时所花费的最少时间，a[i]为单独买第i张票所花时间，如果这个人和上一个人一起买时间花费比较少，那么：dp[i]=dp[i-2]+b[i]; dp[i-2]表示这个票和上一张票一起买了，那么就是截止上一张票之前的那张票所花的时间，加上这两张票一起买所花的时间b[i];

AC代码：

#include
#include
typedef long long ll;
using namespace std;
//int a[100][100];
int a[2000];
int b[2000];
int dp[10000];
int main()
{int n;cin >>n;while(n--){int k;cin >>k;for(int i=1;i<=k;i++){cin >>a[i];}for(int i=2;i<=k;i++){cin >>b[i];}dp[1]=a[1];for(int i=2;i<=k;i++){dp[i]=min(dp[i-1]+a[i],dp[i-2]+b[i]);}int h = dp[k] / 3600;int m = (dp[k] - h * 3600) / 60;int s = (dp[k] - h * 3600 - m * 60);h += 8;if(h < 12)printf("%02d:%02d:%02d am\n", h, m, s);else printf("%02d:%02d:%02d pm\n", h, m, s);}return 0;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！