首页 > ACM题库 > HDU-杭电 > HDU 1795 The least one-动态规划-[解题报告] C++
2013
12-23

HDU 1795 The least one-动态规划-[解题报告] C++

The least one

问题描述 :

  In the RPG game “go back ice age”(I decide to develop the game after my undergraduate education), all heros have their own respected value, and the skill of killing monsters is defined as the following rule: one hero can kill the monstrers whose respected values are smaller then himself and the two respected values has none common factor but 1, so the skill is the same as the number of the monsters he can kill. Now each kind of value of the monsters come. And your hero have to kill at least M ones. To minimize the damage of the battle, you should dispatch a hero with minimal respected value. Which hero will you dispatch ? There are Q battles, in each battle, for i from 1 to Q, and your hero should kill Mi ones at least. You have all kind of heros with different respected values, and the values(heros’ and monsters’) are positive.

输入:

  The first line has one integer Q, then Q lines follow. In the Q lines there is an integer Mi, 0<Q<=1000000, 0<Mi<=10000.

输出:

  For each case, there are Q results, in each result, you should output the value of the hero you will dispatch to complete the task.

样例输入:

2
3
7

样例输出:

5
11

2
2 10 10
0
10
20
30
40
50
60
70
80
90
2 10 3
10
30
40

解题报告转自:http://www.cnblogs.com/2860359561snail/archive/2013/08/16/3261768.html


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。