现在的位置: 首页 > 综合 > 正文

hdu—1260:Tickets

2019年09月03日 ⁄ 综合 ⁄ 共 1009字 ⁄ 字号 评论关闭

此题目讲的是一定的人排队买票,给出每个人买票所需要的时间,和这个人与前一个人一起买票需要的时间,求全部人买完票所需要的最小时间。

由于此题是在[kuangbin带你飞]专题上提交的,所以给出其所在的专题链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=68966#problem/H

思路:显然,此题的各种时间已经给出,则最小的时间量与其买票的人数有关,所以我们可设 dp[i] 表示以 i 为最后一个买完票所需要的最小时间量。影响 dp[i] 的值的只有两种方式,一种是 i 单独买票,此时 dp[i]=dp[i-1]+( i 单独买票的时间);另一种是 i 与前面一个一起买票,则 dp[i]=dp[i-2]+( i 与前面一个一起买票的时间)。

所以,可以得出:dp[i]=min(dp[i],dp[i-2]+d[i]); dp[i]初始化为dp[i]=dp[i-1]+s[i];

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int N,K;
int dp[2010],s[2010],d[2010];//分别存储最小时间量,单独买票时间,一起买票时间

//dp[i]=min(dp[i-2]+d[i],dp[i-1]+s[i]))

int main(){
    cin>>N;
    while(N--)
    {
        cin>>K;
        for(int i=1;i<=K;i++)
            scanf("%d",&s[i]);
        for(int i=2;i<=K;i++)
            scanf("%d",&d[i]);
        dp[0]=0;
        d[1]=0;
        for(int i=1;i<=K;i++)//枚举终点
            if(i==1){
                dp[i]=s[i];
                continue;
            }
            else{
                dp[i]=dp[i-1]+s[i];
                dp[i]=min(dp[i],dp[i-2]+d[i]);
            }
        //cout<<dp[K]<<endl;
        int H,M,S;
        H=dp[K]/3600;
        M=(dp[K]%3600)/60;
        S=dp[K]%60;
        H+=8;
        printf("%02d:%02d:%02d ",H>11?H-12:H,M,S);
        H>11? printf("pm\n"):printf("am\n");
        //cout<<H<<" "<<M<<" "<<S<<endl;
    }
    return 0;
}

 

 

【上篇】
【下篇】

抱歉!评论已关闭.