USACO Section 2.2 Subset Sums

/*
ID: lucien23
PROG: subset
LANG: C++
*/

#include iostream
#include fstream
using namespace std;

int main()
{
	ifstream infile("subset.in");
	ofstream outfile("subset.out");
	if(!infile || !outfile)
	{
		cout  "file operation failure!"  endl;
		return -1;
	}

	int N;
	infile  N;
	
	if (N%4 != 0  (N+1)%4 != 0)
	{
		outfile  0 endl;
		return 0;
	}

	/*
	 * 穷举法,利用位运算,总是超时
	 */
/*	long long maxNum = ((long long)1  N) - 1;
	int count = 0;
	for (long long i=1; imaxNum; i++)
	{
		int sum0, sum1;
		sum0 = sum1 = 0;
		for (int j=0; jN; j++)
		{
			long long temp = 1  j;
			if ((temp  i) == temp)
			{
				sum1 += j + 1;
			} else {
				sum0 += j + 1;
			}
		}
		if (sum0 == sum1)
		{
			count++;
		}
	}
	outfile  count/2  endl;*/

	/*
	 * 动态规划
	 * 要求前n个数分成总和相等的两个子集的方案数
	 * 实际上就是求前n个数中的数可以组成总和为sum=n(n+1)/4的子集的数量
	 * 这就可以用动态规划思想,即从这个子集是否包含n可以分两种情况
	 * 即求前n-1个数中总和为sum-n和总和为sum的子集数目
	 * 设s[i, j]为从前i个数中选择数字组成总和为j的子集的数量,则有
	 * s[i, j] = s[i-1, j] + s[i-1, j-i]    ,    j - i = 0
	 * s[i, j] = s[i-1, j]                     ,    j - i  0
	 */

	int sum = N * (N + 1) / 4;
	long long **s = new long long*[N+1];
	for (int i=0; i=N; i++)
	{
		s[i] = new long long[sum+1]();
	}

	s[1][0] = s[1][1] = 1;
	for (int i=2; i=N; i++)
	{
		for (int j=0; j=sum; j++)
		{
			if (i  j)//不能放i
			{
				s[i][j] = s[i-1][j];
			} else {//可以放i
				s[i][j] = s[i-1][j] + s[i-1][j-i];
			}
		}
	}

	outfile  s[N][sum] / 2  endl;

	return 0;
}

最新回复(0)
/jishu7cSoraCDoBC0TsnUJS7jj3PlevnRO6Uw64GZPuEwYmM_3D4858391
8 简首页