首页 > 其他 > 详细

题解报告:hdu 1260 Tickets

时间:2018-03-07 14:33:36      阅读:199      评论:0      收藏:0      [点我收藏+]

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1260

解题思路:这是一道简单的DP问题,题目的意思就是有两种购票方式,要么采用单独购票,要么采用双人购票。

即得到状态转移方程:dp[i] = min(dp[i - 1] + tim[i], dp[i - 2] + together[i]);两种情况:①前面i-1个人所消耗的时间加上个人当前购票时间;②前i-2个人购票时间加上当前两个人购票的时间;取这两种情况的最小值即为最小花费时间。之后还要对时间显示格式进行处理,这里应该是12小时制,即超过12小时显示为pm且取余12。好了,上代码。

AC代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int tim[2005],together[2005],dp[2005];
 4 int main()
 5 {
 6     int N,K;
 7     cin>>N;
 8     while(N--){//表示N个场景
 9         cin>>K;//表示总人数
10         for(int i=1;i<=K;i++)cin>>tim[i];//读入单个人购票消耗时间
11         for(int i=1;i<=K-1;i++)cin>>together[i];//读入两人购票消耗的时间
12         dp[0]=0,dp[1]=tim[1];//两个人开始的话dp[0]=0,同时dp[1]=tim[1]是选择第一个人进来
13         for(int i=2;i<=K;i++)
14             dp[i]=min(dp[i-1]+tim[i],dp[i-2]+together[i-1]);//递推式
15         int sec=dp[K]%60;//保存秒
16         int minu=(dp[K]/60)%60;//保存分钟
17         int hour=dp[K]/3600+8;//保存时钟
18         int flag=0;//标记是否超过12点
19         if(hour>12){flag=1;hour%=12;}
20         printf("%02d:%02d:%02d ",hour,minu,sec);
21         if(flag)cout<<"pm"<<endl;
22         else cout<<"am"<<endl;
23     }
24     return 0;
25 }

 

题解报告:hdu 1260 Tickets

原文:https://www.cnblogs.com/acgoto/p/8521784.html

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