正如前面所讲的那样，在南非举行的第九届国际奥林匹克信息学竞赛中首次引入了NPC类问题，在杭州举行的NOI98中引入了NOI发展史上的第一道NPC类问题--并行计算。可以说，NPC类问题正在日益引起人们的兴趣。它要求选手根据题意自己建立适当的模型，使程序的解尽量逼近最优解。目前，信息学竞赛所涉及到的少量NPC类问题主要是运用贪心策略或随机化算法去求较优解的。但是对于同一道NPC类问题来说，运用不同的贪心选择所求得的最优解是不同的，不同的贪心选择针对不同的测试数据所得解与最优解的逼近程度也是不同的。所以有关NPC类问题的众多特性以及哪些问题运用贪心策略求得的较优解逼近于最优解仍是需要我们花费大量精力去研究的。信息学奥林匹克的精华-激励创新也许在求解NPC类问题时会得到最大程度的体现。

　　七、 总结

　　通过对贪心策略的分析，大家可以看出：贪心策略作为一种高效算法，广泛地应用与信息学奥林匹克竞赛中。即使表面上看起来与贪心策略关系甚微的题目，运用贪心算法也可使程序的运行效率大大提高。因此，深刻理解贪心策略的数学模型、特点、理论基础、尤其是运用其基本思想解决具体问题是十分重要的。希望本文能给参赛选手以一定的启发。

　　【附 录】

　　【参考书目】

　　１　《实用算法的分析与程序设计》
　　　　吴文虎，王健德编著，电子工业出版社，ISBN 7-5053-4402-1
　　２　《计算机算法导引》
　　　　卢开澄编著，清华大学出版社，ISBN 7-302-02277-1
　　3、 《国际大学生程序设计竞赛试题解析》
　　　　王建德，柴晓路编著，复旦大学出饭社 ISBN 7-309-02141-X/T·210

　　【部分试题及源程序】

　　1、 吉尔的又一个乘车问题：

　　Input file:jill.in

　　Jill likes to ride her bicycle, but since the pretty city of Greenhills where she lives has grown, Jill often uses the excellent public bus system for part of her journey. She has a folding bicycle which she carries with her when she uses the bus for the first part of her trip. She follows the bus route until she reaches her destination of she comes to a part of the city she does not like. In the latter event she will board the bus to finish her trip.

　　Through years of experience, Jill has rated each road on an integer scale of "niceness". Positive niceness values indicate roads Jill likes; negative values are used for roads she does not like. Jill plans where to leave the bus and start bicycling, as well as where to stop bicycling and re-join the bus, so that the sum of niceness values of the roads she bicycles on is maximized. This means that she will sometimes cycle along a road she does not like, provided that it joins up two other parts of her journey involving roads she likes enough to compensate. It may be that no part of the route if suitable for cycling so that Jill takes the bus for its entire route. Conversely, it may be that the whole route is so nice Jill will not use the bus at all.

　　Since there are many different bus routes, each with several stops at which Jill could leave or enter the bus, she feels that a computer program could help her identify the best part to cycle for each bus route.

　　INPUT

　　The input file contains information on several bus routes. The first line of the file is a single integer b representing the number of route descriptions in the file. The identifier for each route (r) is the sequence number within the data files,1≤r≤b. Each route description begins with the number of stops on the route : an integer s, 2≤s≤20,000 on a line by itself. The number of stops is followed by s-1 lines, each line i(1≤i≤s) is an integer ni representing Jill's assessment of the niceness of the road between the two stops i and i+1.

　　OUTPUT

　　For each route r in the input file, your program should identify the beginning bus stop i and the ending bus stop j that identify the segment of the route which yields the maximal sum of niceness m=ni+ni+1+…+nj-1.If more than one segment is maximally nice, choose the one with longest cycle ride(largest j-i). To break ties in longest maximal segments, choose the segment that begins with the earliest stop(lowest i).For each route r in the input file, print a line in the form:
The nicest part of route r is between stops i AND j.

　　However, if the maximal sum is not positive, your program should print:
Route r has no nice parts.

　　INPUT SAMPLE

　　3
　　3
　- 1
　6
　10
4
5
　4
3
　4
　4
4
4
　　- 5
4
2
3
4

　　OUTPUT SAMPLE

　　The nicest part of route 1 is between stops 2 and 3
　　The nicest part of route 2 if between stops 3 and 9
　　Route 3 has no nice parts


　　相关链接：
　　　　　　　贪心策略的特点与在信息学竞赛中的应用(一)
　　　　　　　贪心策略的特点与在信息学竞赛中的应用(二)
　　　　　　　贪心策略的特点与在信息学竞赛中的应用(三)
　　　　　　　贪心策略的特点与在信息学竞赛中的应用(四)
　　　　　　　贪心策略的特点与在信息学竞赛中的应用(五)
　　　　　　　贪心策略的特点与在信息学竞赛中的应用(六)