[CTSC2006] 投篮游戏

题目描述

在大学里，体育课有很多门，每个人都可以选自己最喜欢的项目。King 这学期选的是篮球，因为篮球课的老师是一个十分有趣的人。

上课的第一天，老师宣布了这门课的评分规则：

有 $n$ 个篮球（ $n\ge m$ ），老师事先在每个球上写了一个整数（不一定相同，绝对值小于 $10000$ ）。有 $m$ 个篮，每个篮板上有一个计分器，显示一个整数。一个学生开始考核前先将所有计分器显示值赋为 $1$ 。

每个学生考核时要进行 $n$ 次投篮：选择任意一个篮球投向任意一个篮。最后他必须将所有球全部投出且每个球恰好投出一次，要求每个篮至少被投进过一次。

如果学生将一个写有整数 $x$ 的篮球投进了某个计分器显示为y的篮，则该篮板上的计分器显示值将从 $y$ 变成 $y\times x$ 。

一个学生的原始得分 $S$ 定义为 $m$ 个计分器的显示值之和，如果 $S$ 越大则老师给这个学生的最终打分越高（事实上，老师根据名次按照正态分布给分，但此超出本题了讨论范围）。

King 是一个神投手，他保证能将 $n$ 个球全都投进。但是 King 的数学十分糟糕，他不知道该如何安排投篮，才能使得自己的原始得分最大，你能帮帮他吗？

输入有多组数据，每组数据有两行：

第一行两个整数 $n$ ， $m$ 。

第二行 $n$ 个整数，用一个空格分开，表示老师在 $n$ 个篮球上分别写下的整数。

文件以 0 0 结尾。一个文件中最多只有 $10$ 组数据。

每组数据一行，包含一个整数 $S_{max}$ ，表示最大可能的原始得分。

提示： $S_{max}$ 可能超过任何基本整数类型。 $S_{max}$ 也可能比 $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

【约定】

【样例说明】

第一组数据有多解，其中一解为： $(0,0)(-1,-2,1,2,3,2,10,1)$ 。

第二组数据有多解，其中一解为： $(0,0)(1,1)(-1,-2,2,3,2,10)$ 。

2024/12/11 20:06