简答题 偏难
#16946

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

学习小组

3.2.3 输出格式

输出一行,一个整数,表示所有划分方案中,学习小组综合讨论积极度之和的最大值。

3.2.4.1 输入样例 1

4
2 1 3 2
1 5 6 3

3.2.4.2 输出样例 1

12

3.2.4.3 输入样例 2

8
1 3 2 4 3 5 4 6
0 2 5 6 4 3 3 4

3.2.4.4 输出样例 2

21

未登录也能判分,登录后才会记录
答案与解析
正确答案:<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 &gt; 1 else 0         if diff &lt; 0:             break         # 假设我们考虑用掉了k个学生,只需要考虑k&gt;=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>
这道题暂未补解析。