首页 > 其他 > 详细

【HDU - 1260 】Tickets (简单dp)

时间:2020-02-28 16:01:40      阅读:58      评论:0      收藏:0      [点我收藏+]

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代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x, y) memset(x, y, sizeof(x))
#define Maxn 2000+10
using namespace std;
int n,k;
int a[Maxn];
int b[Maxn];
int dp[Maxn];
int main()
{
    cin>>n;
    while(n--)
    {
        MEM(dp,0);//初始化
        cin>>k;
        for(int i=1; i<=k; i++)
            cin>>a[i];
        for(int j=2; j<=k; j++)
            cin>>b[j];
        dp[1]=a[1];
        dp[2]=min(a[1]+a[2],b[2]);
        for(int i=3; i<=k; i++)//从第三人开始dp
            dp[i]=min(dp[i-1]+a[i],dp[i-2]+b[i]);
        int h=dp[k]/3600+8;//计算时间
        int m=dp[k]%3600/60;
        int s=dp[k]%60;
        if(h>12)
            printf("%02d:%02d:%02d pm\n", h-12, m, s);
        else
            printf("%02d:%02d:%02d am\n", h, m, s);
    }
    return 0;
}

 

 

 

【HDU - 1260 】Tickets (简单dp)

原文:https://www.cnblogs.com/sky-stars/p/12376844.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!