自动搬运

查看原文

来自洛谷，原作者为

	Kalium I guess the side of paradise.

搬运于2025-08-24 21:40:11，当前版本为作者最后更新于2021-08-07 22:07:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P2663 越越的组队题解

前言：

这很有可能是我最后一篇博文，当然，不是最后一篇也是倒数几篇了，祝我 whk 安好吧。

题意：

在 n 个人中选出一半，要求选出人的分数和不超过全班分数和的一半下的最大分数。

思路：

这一看就很背包。

但是，看见这讨厌的一半，我们很难控制一半这玩意。

但作为一道普及-，还是很容易想出将 $dp[i][j]$ 表示为前 i 个人是否得到 j 分。

那么转移方程便显得简单，就是模板，只不过需要多来一层控制人数的循环罢了：

$dp[j][k] |= dp[j - 1][k - a[i]]$。

最后来遍历一遍分数，判断 $dp[n >> 1][i]$ 可不可行即可。

代码：

#include <iostream>
#include <cstdio>

using namespace std;

int n;

int a[107];

int dp[107][10007];

int sum;

inline int maxa(int a, int b) {
	if (a > b)
		return a;
	return b;
}

int main() {
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i ++) {
		scanf("%d", &a[i]);
		
		sum += a[i];
	}
	
	dp[0][0] = 1; 
	
	for (int i = 1; i <= n; i ++) {
		for (int j = i; j >= 1; j --) {
			for (int k = sum >> 1; k >= a[i]; k --)
				dp[j][k] |= dp[j - 1][k - a[i]];
		}
	}
	
	for (int i = sum >> 1; i >= 0; i --) {
		if (dp[n >> 1][i]) {
			printf("%d\n", i);
			return 0;
		}
	} 
}

结语：

麻烦管理员，请允许我废话几句，我怕以后就没博客发上来了。

其实学 OI 到现在，我也不明白为什么在 1 年前已经被淘汰时还要再坚持，或许只是内心的执着，亦或是内心的不甘，然而在新的一年 csp 的前一个月，我终究还是在纠结着要不要参加，学 OI 或许要抵抗许许多多的障碍，家长就是一个难过的关，可能由于家长，我没法去今年的 csp，但我还是祝愿学 OI 的那些巨佬们说：

$Wish$ $you$ $never$ $grow$ $old$.

算是勉励自己吧。