题意：给定整数N，求出将集合[1...N]划分成两组，使得两组和相等的方案的个数
解法：
直接枚举时间复杂度达不到要求。采用递推的方法，回忆经典的背包问题
f[i][v] = max{f[i - 1][v], f[i - 1][v - c[i]] + w[i]}即，第i个物品选或者不选，结合前i-1种物品的情况可以递推出所有的结果
将本题转换一下， 所有数的和为sum，那么每一组的和必为sum /2 （如果sum是偶数），问题就是：在[1...N]的集合中找到数字之和
为sum /2 的方案个数，
状态变量： f[i][sum] 在[1...i]集合中和为sum的方案的个数
状态转移： f[i][sum] = f[i - 1][sum] + f[i - 1][ sum - i] 不是一个寻优问题，是一个递推的过程，
递推法求解：采用类似01背包优化空间复杂度的方法f[v] = f[v] + f[v - i]，初始化f[0] = 1 即寻找所有数使得和为0的方案数（1个，就是都不要）
注意f数组不能用int
/* ID: lsswxr1 PROG: hamming LANG: C++ */ #include <iostream> #include <vector> #include <map> #include <list> #include <set> #include <deque> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <cctype> #include <cstdio> #include <iomanip> #include <cmath> #include <cstdio> #include <string> #include <cstring> #include <fstream> using namespace std; #define USACO #ifdef USACO #define cin fin #define cout fout #endif ////////////////////////////////////////////////////////////////////////// ///宏定义 const int INF = 1000000000; const int MAXN = 40001; const int maxn = MAXN; ///全局变量 和 函数 int N; int main() { #ifdef USACO ofstream fout ("hamming.out"); ifstream fin ("hamming.in"); #endif while (cin >> N) { int tot = (N + 1) * N / 2; if (tot % 2 != 0) { cout << 0 << endl; continue; } else { int sum = tot / 2; long long d[500]; memset(d, 0, sizeof(d)); d[0] = 1; //选择和为0的方案数 for (int i = 1; i <= N; i++) { for (int V = sum; V - i >= 0; V--) { d[V] = d[V] + d[V - i]; } } cout << d[sum] / 2 << endl; } } ///结束 return 0; }