bzoj#P1155. [CTSC2006]投篮游戏shooting
[CTSC2006]投篮游戏shooting
题目描述
在大学里,体育课有很多门,每个人都可以选自己最喜欢的项目。King 这学期选的是篮球,因为篮球课的老师是一个十分有趣的人。
上课的第一天,老师宣布了这门课的评分规则:
有 个篮球,老师事先在每个球上写了一个整数。有 个篮,每个篮板上有一个计分器,显示一个整数。一个学生开始考核前先将所有计分器显示值赋为 。每个学生考核时要进行 次投篮:选择任意一个篮球投向任意一个篮。最后他必须将所有球全部投出且每个球恰好投出一次,要求每个篮至少被投进过一次。如果学生将一个写有整数 的篮球投进了某个计分器显示为 的篮,则该篮板上的计分器显示值将从 变成 。一个学生的原始得分 定义为 个计分器的显示值之和,如果 越大则老师给这个学生的最终打分越高(事实上,老师根据名次按照正态分布给分,但此超出本题了讨论范围)。King 是一个神投手,他保证能将 个球全都投进。但是 King 的数学十分糟糕,他不知道该如何安排投篮,才能使得自己的原始得分最大,你能帮帮他吗?
输入格式
输入有多组数据,每组数据有两行:
第一行两个整数 。
第二行 个整数,用一个空格分开,表示老师在 个篮球上分别写下的整数。文件以 0 0
结尾。一个文件中最多只有 组数据。
输出格式
每组数据一行,包含一个整数 ,表示最大可能的原始得分。
10 2
0 -1 -2 0 1 2 3 2 10 1
10 3
0 -1 -2 0 1 2 3 2 10 1
0 0
240
241
数据规模与约定
对于 的数据,。
对于 的数据,,初始每个球上的数的绝对值不超过 。
可能超过任何基本整数类型,也可能为负数。