当前位置:网站首页>HDU - 1260 Tickets(线性DP)
HDU - 1260 Tickets(线性DP)
2022-07-07 21:53:00 【WA_自动机】
HDU - 1260 Tickets(线性DP)
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:
- An integer K(1<=K<=2000) representing the total number of people;
- K integer numbers(0s<=Si<=25s) representing the time consumed to buy a ticket for each person;
- (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
题意:有K个人排队购买电影票,每个人可以选择自己购买或者和相邻的人组成两人小队一起购买,单独购买的时间为si,组队购买从第2个人开始,和前一个人一起购买花费的总时间是di(时间单位为秒)。8点开始售票,问所有人买到票的最早结束时间(12小时制,上午为am,下午为pm)。
- 状态表示:
dp[i]
表示前i
个人买票花费最少总时间 - 动态转移:当第i个人买票时,有两种选择,自己单独购买或者和前一个人组队购买
- 单独购买:
dp[i-1] + s[i]
(s[i]表示第i个人单独购买花费时间) - 组队购买:
dp[i-2] + d[i]
(d[i]表示第i个人和前一个人组队购买花费时间) - 状态转移方程
dp[i] = min(dp[i-1] + s[i], dp[i-2] + d[i])
#include<iostream>
using namespace std;
const int N = 2010;
int dp[N],a[N],b[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int k;scanf("%d",&k);
for(int i=1;i<=k;i++) scanf("%d",&a[i]);
for(int i=2;i<=k;i++) scanf("%d",&b[i]);
dp[1]=a[1],dp[2]=min(a[1]+a[2],b[2]);
for(int i=3;i<=k;i++)
dp[i]=min(dp[i-1]+a[i],dp[i-2]+b[i]);
int h=8+dp[k]/3600,m=dp[k]%3600/60,s=dp[k]%60;
printf("%02d:%02d:%02d am\n",h,m,s);
}
return 0;
}
边栏推荐
- SAP HR reward and punishment information export
- Dependency injection 2 advantage lifecycle
- C simple question 2
- [untitled]
- go time包常用函数
- UE4_ Ue5 combined with Logitech handle (F710) use record
- 0-1 knapsack problem
- Mobile heterogeneous computing technology - GPU OpenCL programming (basic)
- postgis学习
- Lm12 rolling heikin Ashi double K-line filter
猜你喜欢
Installing gradle
SAP memory parameter tuning process
Markdown
2022 certified surveyors are still at a loss when preparing for the exam? Teach you how to take the exam hand in hand?
Svn relocation
Take you hand in hand to build Eureka server with idea
Three questions TDM
C cat and dog
Take you hand in hand to build feign with idea
B_QuRT_User_Guide(36)
随机推荐
[experiment sharing] log in to Cisco devices through the console port
[STM32 + esp-12s connect Tencent cloud IOT development platform 1] creation of cloud platform and burning of at firmware
神奇快速幂
C - Fibonacci sequence again
Extended tree (I) - graphic analysis and C language implementation
Mobile heterogeneous computing technology - GPU OpenCL programming (basic)
SAP HR family member information
UE4_ Ue5 panoramic camera
Solution of intelligent supply chain collaboration platform in electronic equipment industry: solve inefficiency and enable digital upgrading of industry
B_QuRT_User_Guide(38)
USB (XIV) 2022-04-12
[summary] some panels and videos seen
B_ QuRT_ User_ Guide(39)
Navicat connects Oracle
Extract the file name under the folder under win
Slam interview summary
Anti climbing means cracking the second
SAP 内存参数调优过程
Live-Server使用
Installing gradle