首页 > ACM题库 > HDU-杭电 > Hdu 1414 银河跳舞机大赛 待解决 [解题报告] C++
2013
12-10

Hdu 1414 银河跳舞机大赛 待解决 [解题报告] C++

银河跳舞机大赛

问题描述 :

怀特先生(见ACM/ICPC Asia Regional 2001, Shanghai)通过他的跳舞机(Dance Dance Revolution,DDR)减肥成功,他非常感激他的DDR,想把他的减肥经验推广,于是开了一个公司专门生产跳舞机。
由于他公司生产的跳舞机质量非常优秀,这些跳舞机销往银河系各地,各个星球上的人都非常喜欢它们,整个银河系都掀起了跳舞机热。银河体育联盟决定在银河系范围内举行一次银河跳舞机大赛。参加这次比赛的选手来自那美克星、ShiningStar星、X星、塞亚星…当然还有东道主地球。

由于比赛的奖品非常吸引人――一辆地球中国产的“红旗牌”时光穿梭机,每个选手都将使出浑身解数来争取这个奖品。

选手们拥有不同数量的腿,但是最多四条而且每个腿上只有一个脚。比如:地球人只有两个腿,那美克星人有四个腿,X星人三条、塞亚星人一条…
为此,怀特先生的公司专门为比赛设计了一种跳舞机,这种跳舞机上最多有15个踏板。之中必有一个是编号为ZERO的,它非常大,可以让一个选手的所有脚都站在上面,而且位于整个跳舞机的中心区域;其余的编号为1..P(P ≤ 14),它们均匀地分布在ZERO踏板周围,但是都非常小,每个只能容纳一个脚。
比赛的规则是这样的:

比赛开始前,选手可以将自己的脚踩在任意的踏板上,但是除了ZERO踏板,其余的踏板只能踩一个脚。

然后,播放一首长度为T秒的舞曲(例如:Smile组合的《Butterfly》),在歌曲播放期间,跳舞机的指令会提示选手在某些整秒时刻踩某些踏板。这时选手可以选择起跳并移动他的K(K ≤ P)个脚去踩别的踏板。但是起跳和移动会花费选手D + [K / 2]的时间(这里D表示起跳延时,“[K / 2]”表示K整除2),也就是说他需要花这么长时间才能将K个脚移动到目的区域。如果选手只是在原地起跳,没有移动他的腿的话,只花费D的时间,因为此时他没有去踩别的踏板,K = 0。

当然,选手可以选择站在原地不动,虽然这样做会引起其他选手的严重BS、全场观众的一片嘘声以及铺天盖地仍来的鸡蛋、青菜、萝卜…

另外,如果选手愿意,他也可以将他的一些或者全部脚移动到ZERO区域。

由于参赛的选手都是各个星球的精英,所以它们个个体力充沛,即使刚刚落地,也可以马上进行下一个动作。

如果选手在规定时刻踩了跳舞机提示的那些踏板,那么选手就会得到1分。例如:1秒的时刻,跳舞机提示踩1、2两个踏板,选手做到了(只要有任意两个脚踩在1、2踏板上),这时他的得分会增加1。
判断选手是否可以得分是由装在跳舞机踏板上的传感器来完成的,这些传感器只有在选手起跳的时候才会工作,站在原地不动是不会使它们工作的。一旦舞曲结束,该选手的比赛就结束。

由于比赛选手的腿的数量不一致,会引起不公平,组委会决定比赛以选手的实际得分占他可以得的分数的最高值的比例来判胜负。

可是根据跳舞机踏板的数目、每个选手脚的数目、起跳延时、舞曲的时间、跳舞机的指令序列来计算每个选手可以得到的最大得分对于手工计算还是十分浩大的工程,所以组委会邀请你,杭州电子科技大学聪明的ACMer,写一个程序帮忙计算一下,如果你顺利完成了这个任务,那么奖品嘛…当然是一个由PLMM送来的AC的气球咯!

输入:

测试数据将是多组的,而且每组之间都会有一个空行分隔。
每组测试数据的第一行是五个整数P、F、D、T、M。
P(1 ≤ P ≤ 14)表示跳舞机的踏板数,P = 0 表示输入结束
F(1 ≤ F ≤ 4,F ≤ P)表示选手脚的数量
D(1 ≤ D)表示起跳延时
T(1 ≤ T ≤ 300)表示舞曲的时间
M(1 ≤ M ≤ 300,M ≤ T)表示跳舞机的指令数
接下来,是M行跳舞机的指令,每条指令的格式如下:
t k a1 a2 … ak
其中t表示这条指令是t(1 ≤ t ≤ T)秒时刻的指令,k(1 ≤ k ≤ F)表示指令要求踩的踏板的总数,a1 – ak(1 ≤ ai ≤ P,1 ≤ i ≤ k)表示要求踩a1 – ak号踏板。

输出:

输出能够得到的最大的分数,单位:POINT。

样例输入:

2 1 1 4 1
1 1 1

2 1 1 4 3
1 1 1
2 1 1
3 1 1

0 12 3 29 3
1 1 1
1 1 1
1 1 1

样例输出:

1 POINT.
3 POINTS.


  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。