当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1206:劲乐团

题目描述
劲乐团是这样一个游戏:当游戏开始时,一边播放背景音乐,一边从上至下不断随着音乐掉落Note。(Note是音乐游戏的术语)当该Note掉落至最底部时,则按下对应的键就可以击中该Note并得分。击中的时间越准确得分越高。准确击中可以得到一个COOL,时间稍微有些偏差可以得到一个GOOD。偏差更多或者未击中得到MISS。一个COOL可以得10分,一个GOOD可以得5分。(注意:如果当某一个键被推迟或提前按下时,该位置正好有另一个Note,那么被响应的将是出现较早的那个音符。)
Gardon是劲乐团的高手,正常情况下他可以顺利完成任何难度的歌曲。因此他想让游戏变的更富有挑战性,他决定使用五个手指来弹七个按键的歌曲。这就意味着他的手必须来回移动来击中七个位置的音符。
正常情况下,Gardon采用键盘上的A、S、D、F、J、K、L七个键来对应七个位置,现在Gardon并不打算更改它,只是他用左手的三个手指来操纵ASDF四个键,右手的两个手指操作JKL三个键。
Gardon反应时间的最短间隔被称做一个Tick,一个Tick内,他可以按下一些键,也可以将手指移动,也可以在移动一些手指的同时按下另一些键。但是:正在被移动的手指不能按下任何键,不论是移动的起始点还是终点。恰好,劲乐团对于按键准确程度的判断也是以Tick为单位:正好在该Tick时击中得到COOL,早或者晚一个Tick都将得到GOOD。
游戏一开始时,Gardon的手可以放在任意位置,比如图中的示例,Gardon的手可以放在1、3、4、5、6五个键上,在第四个音符按下的同时将第二个手指从键3上移动到键2上,并完成后面的内容。
注意:不能将手移开,也不能变换手指的顺序,就是说:手指1只能放在键位1、2上,手指2只能放在键位2、3上,手指3只能放在键位3、4上,并且不同的手指不能放在一个键上。一次可以将数个手指同时移动,例如当分别放在1 2 3 5 6的时候,可以同时移动,分别到1 3 4 6 7位置上。并且左手手指不能放到5、6、7位置,右手手指不能放到1、2、3、4位置。
现在Gardon面临了这样一个问题:因为有的时候Note太多或者太复杂,他很难使用五个手指打出全部的COOL,所以他想请你帮忙写个程序,来计算下对于一首歌曲,他最多可以拿到多少分,让他好有个目标来进行练习。


输入解释
输入包含多组数据,每组数据表示了一首歌曲的所有Note的信息,这些信息是Gardon从劲乐团的游戏文件中得到的。信息的格式是这样的:
第一行里有两个整数N和M,N表示了整个歌曲的长度(单位是Tick),M表示了所有Note的数目。(N<=10000000,M<=2821)
接下来M行每行有两个数 Ti和Pi表示了一个Note的信息。Ti是该Note到达底部的时间(单位是Tick),Pi是该Note的位置(1<=Ti<=N,1<=Pi<=7)。输入已经按照Ti排序,没有Ti和Pi都相同的两个Note。
注意:游戏开始前(<0)和结束后(>N)时按键无效。
输出解释
对于输入的每组数据,只有一个数字,表示Gardon能拿到的最高分数。
输入样例
7 9
1 6
2 5
3 3
4 1
5 2
6 1
7 4
7 5
7 7
输出样例
90


就是图中的示例。一开始手放在1、3、4、5、6上,在按下5位置的音符的同时将6位置的手指移到7位置,在按下1位置音符的同时将3位置
的手指移到2位置,这样所有的Note都能打出COOL,一共是90分。
来自杭电HDUOJ的附加信息
Author Gardon
Recommend JGShining

该题目是Virtual Judge题目,来自 杭电HDUOJ

题目来源 Gardon-DYGG Contest 2

源链接: HDU-1206

最后修改于 2020-10-25T22:42:53+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
6000/3000MS(Java/Others) 65536/32768K(Java/Others)