题解【洛谷 P1466 [USACO2.2]集合 Subset Sums】

题目传送门

设 \(sum=1+2+3+4+\dots+n=\dfrac{n(n+1)}{2}\)。

如果 \(2\nmid sum\)，则显然没有方案。
如果 \(2\mid sum\)，则这两个集合的和必为 \(\dfrac{sum}{2}\)。

将 \(\dfrac{sum}{2}\) 作为容量跑 0-1 背包即可。

Code:

#include<iostream>

using namespace std;

const int N=45,SUM=785;

typedef long long ll;  //必须开 long long/dk

ll dp[SUM],n,sum;

int main()

{

	cin>>n;

	sum=(1+n)*n/2; //计算 sum

	if (sum&1){cout<<0;return 0;}  //特判

	sum/=2; dp[0]=1;  //初始化

	for (int i=1;i<=n;i++)

		for (int j=sum;j>=0;j--)

			if (j>=i) dp[j]+=dp[j-i];  //i 为重量，价值为 0，算方案数要将 max 换成 sum。

	cout<<dp[sum]/2;  //输出要 /2

	return 0;

}

巴特西

题解【洛谷 P1466 [USACO2.2]集合 Subset Sums】

最新文章

热门文章