题目：
对于从1到N (1 <= N <= 39) 的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，每个子集合的所有数字和是相等的：{3} 和 {1,2}这是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数） 如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分法的子集合各数字和是相等的:{1,6,7} 和 {2,3,4,5} {注 1+6+7=2+3+4+5}{2,5,7} 和 {1,3,4,6}{3,4,7} 和 {1,2,5,6}{1,2,4,7} 和 {3,5,6}给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出（不能打表）。
输入格式：
输入文件只有一行，且只有一个整数N
输出格式：
输出划分方案总数，如果不存在则输出0。
样例： SAMPLE INPUT
7
SAMPLE OUTPUT
4
思路:
动态规划: f[i][j]-选到第i个时集合一和为j的方案数 f[i][j]+=f[i-1][j-i] for(i=2;i<=n;i++) for(j=g;j>=1;j- -) if(j>=i) f[i][j]=f[i-1][j-i]; 简化得: f[i]+=f[i-j]
代码:
# include<cstdio># include<cstdlib># include<iostream># include<algorithm>using namespace std;long long ans=0,n,g,f[100101];int main(){ scanf("%d",&n); if(n%4==1 || n%4==2){//如果g为奇数输出0 PRintf("0/n"); return 0; } g=n*(n+1)/4;//求出g f[1]=1;//初始化 f[0]=1; for(int i=2;i<=n;i++) for(int j=g;j>=0;j--)//j翻过来循环(让j-i在j后更新) if(j>=i)f[j]+=f[j-i]; printf("%d/n",f[g]/2);//输出记得/2!!!!!}新闻热点
疑难解答
