food
提交数: 560, 通过率: 12.68%, 平均分: 49
题目描述:
PKS的餐桌是一个长方形 (即第一盘 和第N盘 不相连)上面放着N盘食物,每一盘食物都有其相应饱食值,PKS必须选择其中的不能重叠的(即一盘食物不能吃多次)M段食物来吃(每一段都不能小于1)。他太饿了,他希望能得到最大的饱食值。但是食物可能会有负的饱食值,比如吃了会拉肚子。
输入格式:
第一行 2个正整数 N,M
第二行 N个数 为各个食物可以获得的饱食值
输出格式:
一行 为能得到的最大的饱食值
样例输入:
样例1: 5 1 1 2 3 4 5 样例2: 5 2 5 -1 5 -10 5
样例输出:
样例1: 15 样例2: 14
提示:
20%的数据 n<=100 m=1
20%的数据 n<=100 m=2
20%的数据n<=100000 m=1
40%的数据n<=100000 m=2
时间限制: 1000ms空间限制: 128MB
来源: by pks