OI题库

2．珍贵的项链

  (dividenecklace.pas/c/cpp)

【问题描述】

         有一个电影的主人公(假设叫The Best Killer)走在路上,突然冥王(同样也是财富之神)Hades出现在他面前,给他了一个长为N的环形项链,这个项链由一条金丝把各种稀有之物串接起来,可以理解为,项链串接了从1到N个物品,每个物品拥有一个价值整数W_i,每一个物品占用一个单位,让从中选取K段宝物(不能重叠,但可以每段可以挨着),使得总价值超过Limit,如果超过Limit那么Hades就把他的宝座让给TBK,否则TBK就要和Hades一起去地下了,这时候,正在看电影的你立刻暂停了播放,预算TBK是否要被带走.

【输入】

三个整数N表示项链上有N个物品,第二个整数K表示分成K段,第三个整数Limit含义见题目描述

第二行N个整数表示该物品的价值W_i

【输出】

第一行一个字符串,要么是”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<=10³          K<=10

50%数据N<=10⁴          K<=10

100%数据N<=10⁶       K<=10

其中有40%的数据K=1

100%数据所有数字均不超过2⁶³