首页 > ACM题库 > HDU-杭电 > hdu 4088 Healing待解决[解题报告]C++
2015
04-16

hdu 4088 Healing待解决[解题报告]C++

Healing

问题描述 :

Do you know the popular game World Of Warcraft (WOW) made by Blizzard? Tom plays a Blood Elf Paladin in WOW. The Paladins have 3 kinds of talent trees: Holy, Protection and Retribution.
The Holy Paladins in a team are healers, who provide healing service, heal the wounded; the Protection Paladins in a team are tanks, who attract the enemy’s fire and protect the teammates; the Retribution Paladins in a team are melee damage dealers.
After the version Cataclysm is published, the Retribution Paladins are found weakened by Blizzard. But fortunately, the Holy Paladins become more and more powerful amount the healers.
In order to join the dungeons and raids easier, Tom choose the talent of Holy to be his role’s main talent (because the dungeons and raids are lack of healers). What a nice job the Holy Paladin is! Instead of standing in front of the monsters and enduring the hit, the only thing the Holy Paladins should do is to heal teammates and hardly worry about the monsters would attack them.
Unlike the Retribution Paladins’ operation of "Keyboard Rolling", the Holy Paladins have many spells to use of healing, so that some part of the pressing of some spells would be overlapping with each other. Furthermore, once a spell was cast successfully, it would possibly lead to casting one spell easily, that means you can get a buff which would allow you cast one spell in another way (The spell the buff effects can be anyone he can cast).
It is high-operation-frequency when in the dungeons, so Tom can hardly notice whether he cast a spell successfully or how much he had healed. And Tom really wants to know that, so he turns to you for a favor, asks you to write an Add-On which can help him record the total healing points and which spell brings higher total healing points.
About the spells:
Each spell has a distinct name.
Spell needs Mana Points(MP). You cannot cast the spell when there is not enough mana.
Spell has Cool Down Time. Once you cast a spell successfully, you cannot cast the same spell during the next Cool Down Time.
If you fail to cast a spell, the keys you have pressed can be the prefix of the next spell.
If spell-2 is the suffix of spell-1, then spell-1 is priority.
No two spells can be cast in same moment.
Some spells will lead to some buffs(described above) so that when you press some other keys sequences, you will cast some spells, too. Notice that the buff will exist until you cast the exact spell successfully, no matter you use the buff or not. (In other word, if you get the buff of spell A, then you don’t use the buff but cast the spell A, the buff of spell A will disappear.)
One spell will immediately be cast once it fits the spell condition.
Besides, the Holy Paladins have a talent called Meditation, which will regenerates one mana every second. Meditation will regenerate MP immediately when one second starts. And Tom can press 5 keys every second.

输入:

There are no more than 20 test cases, end by EOF.
In each test case:
First line contains 2 integers N (0<N<=10000) and MP (0<=MP<=100000), indicating there will be N spells and you have MP Mana Points at the beginning and you can have MP Mana Points at most.
Then follows N lines:
Each line contains Spell Name, Spell Press Key Sequence, Spell Mana Cost(MC), Spell Healing Points(HP), and Spell Cool Down Time(CD). The Spell Name is no more than 50 characters; Spell Press Key Sequence is no more than 20 characters and all the characters are capital letters; -MP<=MC<=MP, the spell will regenerate manas if the MC is negative;
0<=HP<=100000; 0<=CD<=1000, notice that here the CD is base on 0.2 second, (For example: If CD=5, then the Spell Cool Down Time is 1 second).
Then follow integer M (M+N<=10000), indicates the buffs may appear.
Then M lines follow:
Each line contains Spell-1 Name, Spell-2 Name, Spell-2′s Another Press Key Sequence, which means when you cast Spell-1, you can get the buff of Spell-2, the effect of the buff is Spell-2′s Another Press Key Sequence. The Spell-1 Name and Spell-2 Name is the Spell Name appear in the N lines, Spell-2′s Another Press Key Sequence is no more than 20 characters and all the characters are capital letters.
The last line is Tom’s press sequence, the length is no longer than 500000 and all the characters are capital letters.

输出:

There are no more than 20 test cases, end by EOF.
In each test case:
First line contains 2 integers N (0<N<=10000) and MP (0<=MP<=100000), indicating there will be N spells and you have MP Mana Points at the beginning and you can have MP Mana Points at most.
Then follows N lines:
Each line contains Spell Name, Spell Press Key Sequence, Spell Mana Cost(MC), Spell Healing Points(HP), and Spell Cool Down Time(CD). The Spell Name is no more than 50 characters; Spell Press Key Sequence is no more than 20 characters and all the characters are capital letters; -MP<=MC<=MP, the spell will regenerate manas if the MC is negative;
0<=HP<=100000; 0<=CD<=1000, notice that here the CD is base on 0.2 second, (For example: If CD=5, then the Spell Cool Down Time is 1 second).
Then follow integer M (M+N<=10000), indicates the buffs may appear.
Then M lines follow:
Each line contains Spell-1 Name, Spell-2 Name, Spell-2′s Another Press Key Sequence, which means when you cast Spell-1, you can get the buff of Spell-2, the effect of the buff is Spell-2′s Another Press Key Sequence. The Spell-1 Name and Spell-2 Name is the Spell Name appear in the N lines, Spell-2′s Another Press Key Sequence is no more than 20 characters and all the characters are capital letters.
The last line is Tom’s press sequence, the length is no longer than 500000 and all the characters are capital letters.

样例输入:

3 10
HolyShock ASDF 5 10 3
Judgements SDFG -10 0 10
LightsOfDawn DFGH 10 25 10
2
HolyShock Judgements G
Judgements LightsOfDawn H
ASDFSDFGH

1 10
WordOfGlory A 1 10 1
0
AAAAAAAA

1 1
HolyLight A 1 10 1
0
AAAAAAAAAA

样例输出:

Case 1:
The Total Healing Point is 35.
LightsOfDawn 25 1
HolyShock 10 1

Case 2:
The Total Healing Point is 40.
WordOfGlory 40 4

Case 3:
The Total Healing Point is 20.
HolyLight 20 2


  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  4. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮