A26918. 学习小组
填空题
困难
知识点
题目描述
学习小组
题目描述
班主任计划将班级里的n名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。观察发现，如果一个学习小组中恰好包含k名同学，则该学习小组的讨论积极度为 ak。
给定讨论积极度 a1,a2…,an，请你计算将这n名同学划分为学习小组的所有可能方案中，讨论积极度之和的最大值。
输入格式
第一行，一个正整数 n，表示班级人数。
第二行，几个非负整数a1,a2…,an，表示不同人数学习小组的讨论积极度。
输出格式
输出共一行，一个整数，表示所有划分⽅案中，学习小组讨论积极度之和的最大值。
样例
输入样例 1
4
1 5 6 3输出样例 1
10输入样例 2
8
0 2 5 6 4 3 3 4输出样例 2
12数据范围
对于 40% 的测试点，保证 1≤n≤ 10。
对于所有测试点，保证1≤n≤1000，0≤ai≤104。
参考答案
# 首先记录同学总数
n = int(input())
# 记录一个小组有k个同学的情况下，讨论积极度
a = [0] + list(map(int, input().split()))
# 0个同学的时候，讨论度为0
dp = [0]
# 遍历同学总数k
for k in range(1, n + 1):
# i,j表示将k个同学分解为i个同学和j个同学两部分
dp.append(0)
for i in range(0, k):
j = k - i
# 核心状态转移公式
dp[k] = max([a[k], dp[i] + dp[j], d[k]])
print(dp[n])
上一题
下一题