P1466 [USACO2.2] 集合 Subset Sums

题目描述对于从 1∼n 的连续整数集合能划分成两个子集合且保证每个集合的数字和是相等的。举个例子如果 n3对于 {1,2,3} 能划分成两个子集合每个子集合的所有数字和是相等的{3} 和 {1,2} 是唯一一种分法交换集合位置被认为是同一种划分方案因此不会增加划分方案总数如果 n7有四种方法能划分集合 {1,2,3,4,5,6,7}每一种分法的子集合各数字和是相等的{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你的程序应该输出划分方案总数。输入格式输入文件只有一行且只有一个整数 n。输出格式输出划分方案总数。输入输出样例输入 #1复制7输出 #1复制4说明/提示【数据范围】对于 100% 的数据1≤n≤39。翻译来自 NOCOW。USACO 2.2代码#include bits/stdc.h using namespace std; long long dp[1000]; int n; int main(){ //freopen(test1.in, r, stdin); //freopen(test2.out, w, stdout); ios::sync_with_stdio(0), cin.tie(0),cout.tie(0); cinn; dp[0]1; int s0; for(int i1;in;i){ si; for(int js;j0;j--){ int xjji; dp[xj]dp[xj]dp[j]; } } if(s%21){ cout0; return 0; } int cs/2; coutdp[c]/2; return 0; }恭喜你又A了一题