HDU-1260 Tickets（dp）

叁歲伎倆 2022-04-25 05:10 105阅读 0赞

**Problem Description:**

Jesus, what a great movie! Thousands of people are rushing to the cinema. However, this is really a tuff time for Joe who sells the film tickets. He is wandering when could he go back home as early as possible.   
A good approach, reducing the total time of tickets selling, is let adjacent people buy tickets together. As the restriction of the Ticket Seller Machine, Joe can sell a single ticket or two adjacent tickets at a time.   
Since you are the great JESUS, you know exactly how much time needed for every person to buy a single ticket or two tickets for him/her. Could you so kind to tell poor Joe at what time could he go back home as early as possible? If so, I guess Joe would full of appreciation for your help.

**Input:**

There are N(1<=N<=10) different scenarios, each scenario consists of 3 lines:   
1) An integer K(1<=K<=2000) representing the total number of people;   
2) K integer numbers(0s<=Si<=25s) representing the time consumed to buy a ticket for each person;   
3) (K-1) integer numbers(0s<=Di<=50s) representing the time needed for two adjacent people to buy two tickets together.

**Output:**

For every scenario, please tell Joe at what time could he go back home as early as possible. Every day Joe started his work at 08:00:00 am. The format of time is HH:MM:SS am|pm.

**Sample Input:**

2
    2
    20 25
    40
    1
    8

**Sample Output:**

08:00:40 am
    08:00:08 am

**题目大意：**

Joe卖电影票，他可以一次性卖一张票也可以连着卖两张票，卖票需要花时间，Joe从早8点开始卖票，Joe想早卖完票早回家，问Joe最早卖完票是在什么时候。

先输入样例的个数N表示一共需要处理N个样例，每个样例的第一行表示需要买票的总人数K，第二行输入的是一个数组表示的是卖单张票给一个人所要花的时间，第三行输入的也是一个数组表示卖两张连着的票给两个人所要花的时间。

**思路：**

Joe**每次卖票都有两种选择，卖单张或者连着卖两张**，但是要保证花的总时间最短，是一个dp（动态规划）问题。卖票卖到一个人的时候，dp方程为**Min(dp\[i-1\]+a\[i\],dp\[i-2\]+b\[i\])**，其中a\[i\]为卖单张票给第i+1个人所要花的时间，b\[i\]为卖两张连着的票给第i个人和第i+1个人所要花的时间。**最后所要花的最短时间就是dp\[K-1\]，即完成第K个人的卖票所要花的最短时间。**最后不要忘记处理时间的输出格式。

**上AC代码：**

#include <stdio.h>
    int n,k;
    int dp[2000];
    int a[2000];
    int b[2000];
    int Min(int a,int b)
    {
        return a<b?a:b;
    }
    int main()
    {
        scanf("%d",&n);
        while(n--)
        {
            int i;
            scanf("%d",&k);
            for(i=0;i<k;i++)
            {
                scanf("%d",&a[i]);
            }
            for(i=1;i<=k-1;i++)
            {
                scanf("%d",&b[i]);
            }
            dp[0]=a[0];
            dp[1]=Min(dp[0]+a[1],b[1]);
            for(i=2;i<k;i++)
            {
                dp[i]=Min(dp[i-1]+a[i],dp[i-2]+b[i]);
            }
            int dert=dp[k-1];
            int h=8,m=0,s=0;
            bool am=true;
            while(dert-60>0)
            {
                m++;
                if(m>=60)
                {
                    m=0;
                    h++;
                    if(h>=12)
                    {
                        am=false;
                        h=0;
                    }
                }
                dert-=60;
            }
            s+=dert;
            printf("%02d:%02d:%02d ",h,m,s);
            if(am)
                printf("am\n");
            else
                printf("pm\n");
        }
        return 0;
    }