Tickets

搬中文

Descriptions:

现在有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

题目链接：
https://vjudge.net/problem/HDU-1260

 

dp[i]表示前i个人需要用的时间   a[i]表示第i个人自己买票的时间   b[i]表示第i个人和第i-1个人买票需要的时间

第i个人他可能自己买（dp[i] == dp[i-1]+a[i])   或者   和前面一个人合买（dp[i] = dp[i-2]+b[i]）

 

AC代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <fstream>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <deque>
  7. #include <vector>
  8. #include <queue>
  9. #include <string>
  10. #include <cstring>
  11. #include <map>
  12. #include <stack>
  13. #include <set>
  14. #define Mod 1000000007
  15. #define eps 1e-6
  16. #define ll long long
  17. #define INF 0x3f3f3f3f
  18. #define MEM(x, y) memset(x, y, sizeof(x))
  19. #define Maxn 2000+10
  20. using namespace std;
  21. int n,k;
  22. int a[Maxn];
  23. int b[Maxn];
  24. int dp[Maxn];
  25. int main()
  26. {
  27.     cin>>n;
  28.     while(n--)
  29.     {
  30.         MEM(dp,0);//初始化
  31.         cin>>k;
  32.         for(int i=1; i<=k; i++)
  33.             cin>>a[i];
  34.         for(int j=2; j<=k; j++)
  35.             cin>>b[j];
  36.         dp[1]=a[1];
  37.         dp[2]=min(a[1]+a[2],b[2]);
  38.         for(int i=3; i<=k; i++)//从第三人开始dp
  39.             dp[i]=min(dp[i-1]+a[i],dp[i-2]+b[i]);
  40.         int h=dp[k]/3600+8;//计算时间
  41.         int m=dp[k]%3600/60;
  42.         int s=dp[k]%60;
  43.         if(h>12)
  44.             printf("%02d:%02d:%02d pm\n", h-12, m, s);
  45.         else
  46.             printf("%02d:%02d:%02d am\n", h, m, s);
  47.     }
  48.     return 0;
  49. }

 

 

 
 
版权声明：本文为sky-stars原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/sky-stars/p/12376844.html