首页 > ACM题库 > HDU-杭电 > HDU 1206 劲乐团-数学相关-[解题报告] C++
2013
12-04

HDU 1206 劲乐团-数学相关-[解题报告] C++

劲乐团

问题描述 :

劲乐团是这样一个游戏:当游戏开始时,一边播放背景音乐,一边从上至下不断随着音乐掉落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

Hint
Hint
就是图中的示例。一开始手放在1、3、4、5、6上,在按下5位置的音符的同时将6位置的手指移到7位置,在按下1位置音符的同时将3位置 的手指移到2位置,这样所有的Note都能打出COOL,一共是90分。

样例给的11很坑,WA了2次

#include <cstdio>
#define maxn 200
using namespace std;
int a[maxn];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int sum=0;
        while(n--)
        {
            int x,y;
            scanf("%d(%d)",&x,&y);
            int j=0;
            while(x)
            {
                a[j++]=x%10;//倒着存取
                x/=10;
            }
            int c=0;
            for(int i=j-1;i>=0;i--)//倒着读取
                c=c*y+a[i];
            sum+=c;
        }
        printf("%d\n",sum);
    }
    return 0;
}


  1. 这个方法是错的,不信你试试:
    20 5
    1 A:9
    1 A:9
    1 A:9
    1 A:6
    1 A:4
    正确答案应该是19,这个答案是18

  2. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count