首页 > ACM题库 > HDU-杭电 > HDU 1260 Tickets-动态规划-[解题报告] C++
2013
12-04

HDU 1260 Tickets-动态规划-[解题报告] C++

Tickets

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

2
2
20 25
40
1
8

样例输出:

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

1.题目

http://acm.hdu.edu.cn/showproblem.php?pid=1260

2.分析

简答DP,类似于走阶梯(走一步还是两步到达终点)的问题,状态转移方为:f[i]=min(f[i-1]+t1[i],f[i-2]+t2[i]);
决策是:前一个、前两个
算出秒数之后利用时间函数转换成具体的时分秒输出即可,大笑

3.复杂度

4.涉及内容

动态规划

5.感想

6.代码

#include <iostream>
#include <time.h>
#include <string.h>
using namespace std;
unsigned int time1[2001];
long time2[2001];
int min(int a,int b)
{
	return a>b?b:a;
}
void converttime(long time,struct tm &t)
{
	int hour=0,minute=0,second=0;
	second=time%60;
	minute=((time-second)/60)%60;	minute%=60;
	hour=(time-second-minute*60)/3600;	hour%=24;
	t.tm_hour+=hour;	t.tm_min+=minute;	t.tm_sec+=second;
}
int main()
{
	freopen("in.txt","r",stdin);
	struct tm t;
	t.tm_year=2013-1900;	t.tm_mon=4;	t.tm_mday=2;
	t.tm_hour=8;	t.tm_min=0;	t.tm_sec=0;	t.tm_isdst=0;
	char str[13];
	int N,K;
	cin>>N;
	while(N--)
	{
		memset(time1,0,sizeof(time1));
		memset(time2,0,sizeof(time2));
		t.tm_hour=8;	t.tm_min=0;	t.tm_sec=0;
		cin>>K;
		for(int i=1;i<=K;++i)
			cin>>time1[i];
		for(int i=1;i<=K-1;++i)
			cin>>time2[i+1];
		for(int i=2;i<=K;++i)
		{
			time1[i]=min(time1[i-1]+time1[i],time1[i-2]+time2[i]);
		}
		converttime(time1[K],t);
		strftime(str,13,"%H:%M:%S %p",&t);  
		cout<<strlwr(str)<<endl;
	}
	return 0;
}

7.参考文献


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3