P4530 [CTSC2006] 投篮游戏

Question

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

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

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

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

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

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

第一行两个整数n,m。

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

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

输出格式
每组数据一行，包含一个整数每组数据一行，包含一个整数s，表示最大可能的原始得分。

提示：
s可能超过任何基本整数类型。
也可能比0小。
输入输出样例
输入 #1复制
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
输出 #1复制
240
241
说明/提示
【约定】

1≤ m≤n≤ 2000

恰有40%的数据满足n≤100

【样例说明】

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

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

Answer 1

这个问题可以通过动态规划来解决。首先，对篮球上的整数进行排序。然后使用一个三维数组dp[i][j][k]，其中i表示处理到第几个篮球，j表示已经投了几个篮球，k表示当前各篮板上的得分情况。
（1）动态规划状态转移方程为：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k]*nums[i])。
（2）其中，dp[i][j][k]表示处理到第i个篮球，已经投了j个篮球，各篮板得分情况为k时的最大得分。
（3）最后结果为max(dp[n][m][k])，其中k是所有篮板得分情况之和。

具体代码实现可以参考下面的伪代码框架：

def maxOriginalScore(n, m, nums):
    # 对篮球上的整数进行排序
    nums.sort()

    # 初始化动态规划数组
    dp = [[[0 for _ in range(80001)] for _ in range(11)] for _ in range(2001)]

    # 动态规划求解
    for i in range(1, n + 1):
        for j in range(1, min(i, m) + 1):
            for k in range(80001):
                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k] * nums[i-1])

    # 计算最大得分
    maxScore = 0
    for k in range(80001):
        maxScore = max(maxScore, dp[n][m][k] + k)

    return maxScore

# 读取输入数据
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    nums = list(map(int, input().split()))

    # 输出结果
    print(maxOriginalScore(n, m, nums))