网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[河南省队2012闫星光]珍贵的项链
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | dividenecklace.in | 输出文件 | dividenecklace.out |
2.珍贵的项链
(dividenecklace.pas/c/cpp)
【问题描述】
有一个电影的主人公(假设叫The Best Killer)走在路上,突然冥王(同样也是财富之神)Hades出现在他面前,给他了一个长为N的环形项链,这个项链由一条金丝把各种稀有之物串接起来,可以理解为,项链串接了从1到N个物品,每个物品拥有一个价值整数Wi,每一个物品占用一个单位,让从中选取K段宝物(不能重叠,但可以每段可以挨着),使得总价值超过Limit,如果超过Limit那么Hades就把他的宝座让给TBK,否则TBK就要和Hades一起去地下了,这时候,正在看电影的你立刻暂停了播放,预算TBK是否要被带走.
【输入】
三个整数N表示项链上有N个物品,第二个整数K表示分成K段,第三个整数Limit含义见题目描述
第二行N个整数表示该物品的价值Wi
【输出】
第一行一个字符串,要么是”Go To the Hell”表示无法找到选取方式使得总价值超过Limit,要么是” New Pluto was born”表示超过了Limit
如果第一行输出了” New Pluto was born”那么下一行输出TBK能取到的最大的价值.
【输入输出样例1】
dividenecklace.in |
dividenecklace.out |
10 3 1 1 3 -5 4 -5 4 -5 3 1 -2 |
New Pluto was born 14 |
【数据范围】
10%数据N<=10 K<=10
40%数据N<=103 K<=10
50%数据N<=104 K<=10
100%数据N<=106 K<=10
其中有40%的数据K=1
100%数据所有数字均不超过263