等和的分隔子集（dp）

晓萌希望将 1 到 N 的连续整数组成的集合划分成两个子集合,且保证每个集合的数字和是相等。

例如,对于 N = 3,对应的集合 1, 2, 3 能被划分成3和1,2两个子集合。

这两个子集合中元素分别的和是相等的。

对于N=3，我们只有一种划分方法，而对于N=7时，我们将有4种划分的方案。

输入格式

输入包括一行，仅一个整数，表示N的值(1≤N≤39)。

输出格式

输出包括一行，仅一个整数，晓萌可以划分对应N的集合的方案的个数。当没法划分时，输出0。

样例输入

样例输出

用dp[i]表示组成i的方案数，类似于背包的转移，转移的时候，记上对应的方案数，而不是权值。

记得最后的答案需要除以2因为会算重复，两个集合相互调换位置了以后又计算了一次。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 using namespace std;
16  
17 LL dp[5010];
18  
19 int main()
20 {
21     
22     int n;
23     scanf("%d",&n);
24     int sum=(1+n)*n/2;
25     dp[0]=1;//初始化 
26     for(int i=1;i<=n;i++)
27     {
28         for(int j=sum;j>=i;j--)
29             dp[j]+=dp[j-i];//记录方案数 
30     }
31     if(sum%2==1) printf("0
");
32     else printf("%d
",dp[sum/2]/2);//记得除以2 
33     
34     return 0;
35 }