简答题
偏难
#16946
学习小组 3.2.3 输出格式 输出一行,一个整数,表示所有划分方案中,学习小组综合讨论积极度之和的最大值。 3.2.4.1 输入样例 1 4 2 1 3 2…
学习小组

3.2.3 输出格式
输出一行,一个整数,表示所有划分方案中,学习小组综合讨论积极度之和的最大值。
3.2.4.1 输入样例 1
3.2.4.2 输出样例 1
3.2.4.3 输入样例 2
3.2.4.4 输出样例 2

答案与解析
正确答案:<pre class="brush:python;toolbar:false">getint = lambda: map(int, input().split())
getints = lambda: list(getint())
# 同学数量
n = int(input())
# 按照讨论积极程度从小到大排序,方便后面计算转移方程
c = sorted(getints())
# 不同分组的基础讨论度
a = [0] + getints()
# 用来进行动态规划的数组
# f[j][k]表示在当前已经用掉k个学生,且包含了j个人数不为1的组的情况下的最大积极度
# 我们在这里使用了滚动数组优化,所以没有题解中的i维度
f = [[0] * (n + 1) for _ in range(n + 1)]
# 考虑人数最少的组不少于i个人的情况
for i in range(n, 0, -1):
# j表示分成了多少个组
# 一共就n个人,所以组的数量绝对不大于n//i+1
for j in range(1, n // i + 1):
# 如果最后一个小组刚刚好有i个人,因为之前的组都有至少i个人,所以新加入的组应该选择第j大和第j小的元素作为极大极小值
diff = c[n - j] - c[j - 1] if i > 1 else 0
if diff < 0:
break
# 假设我们考虑用掉了k个学生,只需要考虑k>=i的情况即可
for k in range(i, n + 1):
# 判断最后一个小组如果刚刚好有i个人能否比
f[j][k] = max(f[j][k], f[j - 1][k - i] + a[i] + diff)
print(max(f[i][n] for i in range(n + 1)))</pre><p><br/></p>
这道题暂未补解析。