主播主播，你们的DP确实强悍，但是我因为看错了题获得了 $O(\frac{nm}{w})$ 的做法。

题目里说所有同盟的和不超过 $1e5$ ，然而我误以为是每个同盟不超过 $1e5$ ，那么和就不超过 $3e7$，普通的 $DP$ 显然过不了了。

不过很显然我们需要记录的 $DP$ 应该就是每一种答案能不能出现，于是就可以上 $bitset$ 了。

然后我们枚举每一个数，把它加进去就是相当于 $S=S|(S<<a_i)$，当然我们加是有限制的，由于在加进来前同盟人数不可超过 $m/2$，所以我们用于左移的数要把高于 $m/2$ 的数都干掉，就好了。

但是这样做还是有问题，不过如果你按照从大到小的顺序加就对了。

代码极短

#include<bits/stdc++.h>
using namespace std;
int a[305];
bitset<30000005>S,T;
//bitset开得太大了，导致获得最裂解，不过如果只开1e5就跑得飞快了
bool cmp(int x,int y){return x>y;
}
int main(){
	int n,m=0;
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		m+=a[i];
	}int stdd=m/2+1;
	sort(a+1,a+1+n,cmp);
//	cout<<stdd<<endl; 
	for(int i=stdd-1; i>=0; i--)T[i]=1;
	S[0]=1;
	for(int i=1; i<=n; i++){
		S|=((S&T)<<a[i]);
	}for(int i=m; i>=stdd; i--){
		if(S[i]){
			cout<<i;
			break;
		}
	}
	return 0;
}

01背包

思路

对于条件三：设武林中共suma人，武林同盟共sum人。

任意一个加入武林同盟的帮派x，需满足sum-x<=suma/2，即x>=sum-suma/2

如果最小x都满足x>=sum-suma/2，那么其他的x必定满足，考虑枚举最小的x

dp

设此时枚举的最小数为x，则sum<=suma/2+x。

将每个帮派人数看成物品质量和价值，将suma/2+x看成背包容量，01背包即可

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long

namespace syr
{
	const ll N = 1e5+10;
    ll n, suma, ans;
    ll a[310], dp[N];
	void work()
	{
		cin>>n;
		for (ll i=1; i<=n; i++) {
			cin>>a[i];
			suma += a[i];
		}
		sort(a+1, a+1+n);
		for (ll i=n; i>=1; i--) { //枚举最小的 
			ll ax = min(suma/2+a[i], suma);
			for (ll k=ax; k>=a[i]; k--)
				dp[k] = max(dp[k], dp[k-a[i]]+a[i]);
			ans = max(ans, dp[ax]);
		}
		cout<<ans<<'\n';
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	syr::work();
	return 0;
}

我们直接可行性背包dp

我们设 $dp_i$ 为有 $i$ 个人是否可能出现，一个小贪心是我们先考虑人数较多的帮派

然后对于一个 $a_i$ ，枚举所有的总人数 $j$ ，如果 $j-a_i>\frac{sum}{2}$ ，肯定不能放，否则直接 $dp_j ~ or ~ dp_{j-a_i}$ ，最后统计答案

dp[0]=1;
	for(int i=n;i>=1;i--){
		for(int j=sum;j>=a[i];j--){
			if(j-a[i]>(sum/2)) continue;
			dp[j]|=dp[j-a[i]];
		}
	}
	for(int i=sum/2+1;i<=sum;i++){
		if(dp[i]) ans=max(ans,i);
	}

非常显然的dp 背包，只不过更新答案的时候要符合题目要求： 1.加入武林同盟的总人数要大于 M 的一半； 2.退出武林同盟，而导致武林同盟中剩余的人数大于 M 的一半，则这个帮派不允许加入。 (dp[j]-a[i])<=(sum>>1)&&dp[j]>(sum>>1)

如果满足，则ans取max。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int n,sum,ans,a[N],dp[N];
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
}
signed main(){
	n=read();
	for(int i = 1;i<=n;i++)a[i]=read(),sum+=a[i];
	sort(a+1,a+1+n);
	ans=0;
	for(int i = n;i>=1;i--){
		for(int j = sum;j>=0;j--){
			if(j>=a[i])dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
			if((dp[j]-a[i])<=(sum>>1)&&dp[j]>(sum>>1))
				ans=max(ans,dp[j]);
		}
	}
	write(ans);putchar('\n');
	return 0;
}

后面是废话不用看

本人应该认真审视自己总是在开数组的时候写错数据范围这件事。本人已经反复在这个极其弱智的问题上丢分了。赛事代码24pts，唯一的问题就在于dp[]开小了。真的崩溃。

dp[j]，j是从总人数sum开始的，甚至题目中还给出了“所有帮派的总人数不超过 100000”，开数组的时候却想当然的开成了N，而N是帮派的数量，显然开小了。发现大样例没有输出，本人很懵，但竟然没有发现是由于数组开小的缘故，值得深刻反省。