当前位置:网站首页>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;
}
边栏推荐
- Solution of intelligent supply chain collaboration platform in electronic equipment industry: solve inefficiency and enable digital upgrading of industry
- How to login and enable synchronization function in Google browser
- USB (XVIII) 2022-04-17
- Display the server hard disk image to the browser through Servlet
- [stm32+esp8266 connects to Tencent cloud IOT development platform 3] stm32+esp8266-01s dynamically registers devices on Tencent cloud (at instruction mode) -- with source code
- Dependency injection 2 advantage lifecycle
- C number of words, plus ¥, longest word, average value
- Jisuan Ke - t3104
- 【汇总】看过的一些Panel与视频
- Possible SQL for Oracle table lookup information
猜你喜欢
[stm32+esp8266 connect Tencent cloud IOT development platform 2] stm32+esp8266-01s connect Tencent cloud
How to change the formula picture in the paper directly into the formula in word
c—线性表
Progress broadcast | all 29 shield machines of Guangzhou Metro Line 7 have been launched
USB (XV) 2022-04-14
Understand TCP's three handshakes and four waves with love
Design and implementation of spark offline development framework
Anxinco EC series modules are connected to the multi protocol access products of onenet Internet of things open platform
B / Qurt Utilisateur Guide (36)
Balanced binary tree [AVL tree] - insert, delete
随机推荐
Open source hardware small project: anxinco esp-c3f control ws2812
ASP. Net query implementation
C - Fibonacci sequence again
企业应用需求导向开发之人力部门,员工考勤记录和实发工资业务程序案例
Enumeration, simulation, and sorting
B_ QuRT_ User_ Guide(36)
B_QuRT_User_Guide(36)
The file format and extension of XLS do not match
数据分析系列 之3σ规则/依据拉依达准则来剔除异常值
C语言学习
SLAM面试总结
Ora-02437 failed to verify the primary key violation
SAP HR labor contract information 0016
Oracle string sorting
Home appliance industry channel business collaboration system solution: help home appliance enterprises quickly realize the Internet of channels
Senior programmers must know and master. This article explains in detail the principle of MySQL master-slave synchronization, and recommends collecting
保证接口数据安全的10种方案
c—线性表
【leetcode】day1
B_ QuRT_ User_ Guide(37)