yuzh的博客

❤ ECUST ❤

0%

平分子集

发表于 更新于 Valine：
参考博客

题目描述

对于从1到N的连续整集合，划分为两个子集合，且保证每个集合的数字和是相等的。因而，划分之后每个子集全的数字应该为n(n+1)/2的一半，即n(n+1)/4由于两个子集中都是整数，所以n*(n+1)必为偶数，则可以设s=n*(n+1),并判断s%4 .则，s/=4是划分之后子集合的数字和；dyn[i]数组表示任意个数加起来等于i的组数。**

题解如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;

int main()
{
	int ans[100];
	memset(ans,0,100);
	int n,s;
	cin>>n;
	s=n*(n+1);
	if(s%4!=0)
	{
		cout<<0<<endl;
		return 0;
	}
	s/=4;
	int i,j;
	ans[0]=1;
	for(i=1;i<=n;i++)
		for(j=s;j>=i;j--)
			ans[j]+=ans[j-i];
	cout<<ans[s]/2<<endl;
	return 1;
}