A22044. 学习小组
填空题
困难
知识点
题目描述
学习小组
题目描述
班主任计划将班级里的 n 名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。班级里的同学依次以 1,2,…,n 编号，第 i 名同学有其发言积极度ci。
观察发现，如果一个学习小组中恰好包含编号为p1,p2,...,pk)的 k 名同学，则该学习小组的基础讨论积极度为ak，综合讨论积极度为ak + max{cp1,cp2,...,cpk} - min{cp1,cp2,...,cpk}，也即基础讨论积极度加上小组内同学的最大发言积极度与最小发言积极度之差。
给定基础讨论积极度a1,a2,...,an，请你计算将这 n 名同学划分为学习小组的所有可能方案中，综合讨论积极度之和的最大值。
输入格式
第一行，一个正整数n，表⽰班级⼈数。
第二行，n 个⾮负整数 c1,c2,...cn，表⽰每位同学的发言积极度。
第三行， n 个⾮负整数a1,a2,...,an，表⽰不同⼈数学习小组的基础讨论积极度。
输出格式
输出一行，一个整数，表⽰所有划分方案中，学习小组综合讨论积极度之和的最⼤值。
样例
输入样例 1
4
2 1 3 2
1 5 6 3输出样例 1
12输入样例 2
8
1 3 2 4 3 5 4 6
0 2 5 6 4 3 3 4输出样例 2
21数据范围
对于40的测试点，保证ci=0。
对于所有测试点，保证1≤n≤300， 0≤ci≤104 ， 0≤ai≤104 。
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 305;
int n;
int c[N], a[N];
int f[N][N];
int ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(c + 1, c + n + 1);
for (int i = n; i >= 1; i--) {
for (int j = i; j <= n; j++) {
for (int k = j; k <= n; k++) {
int diff = 0;
if (i > 1) diff = c[n - j + 1] - c[j];
f[j][k] = max(f[j][k], f[j - 1][k - i] + a[i] + diff);
if (k == n) ans = max(ans, f[j][k]);
}
}
}
printf("%d\n", ans);
return 0;
}
上一题
下一题