【HDU - 1260 】Tickets （简单dp）

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

20 25

40

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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <string>
#include 
#include 
#include 
#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;
}

动态规划简单dp

【HDU - 1260 】Tickets （简单dp）

Tickets

相关

标签