P1466 集合 Subset Sums【洛谷算法习题】

P1466 集合 Subset Sums网页链接P1466 集合 Subset Sums题目描述对于从1 ∼ n 1\sim n1∼n的连续整数集合能划分成两个子集合且保证每个集合的数字和是相等的。举个例子如果n 3 n3n3对于{ 1 , 2 , 3 } \{1,2,3\}{1,2,3}能划分成两个子集合每个子集合的所有数字和是相等的{ 3 } \{3\}{3}和{ 1 , 2 } \{1,2\}{1,2}是唯一一种分法交换集合位置被认为是同一种划分方案因此不会增加划分方案总数如果n 7 n7n7有四种方法能划分集合{ 1 , 2 , 3 , 4 , 5 , 6 , 7 } \{1,2,3,4,5,6,7 \}{1,2,3,4,5,6,7}每一种分法的子集合各数字和是相等的{ 1 , 6 , 7 } \{1,6,7\}{1,6,7}和{ 2 , 3 , 4 , 5 } \{2,3,4,5\}{2,3,4,5}{ 2 , 5 , 7 } \{2,5,7\}{2,5,7}和{ 1 , 3 , 4 , 6 } \{1,3,4,6\}{1,3,4,6}{ 3 , 4 , 7 } \{3,4,7\}{3,4,7}和{ 1 , 2 , 5 , 6 } \{1,2,5,6\}{1,2,5,6}{ 1 , 2 , 4 , 7 } \{1,2,4,7\}{1,2,4,7}和{ 3 , 5 , 6 } \{3,5,6\}{3,5,6}给出n nn你的程序应该输出划分方案总数。输入格式输入文件只有一行且只有一个整数n nn。输出格式输出划分方案总数。输入输出样例 #1输入 #17输出 #14说明/提示【数据范围】对于100 % 100\%100%的数据1 ≤ n ≤ 39 1\le n \le 391≤n≤39。翻译来自 NOCOW。USACO 2.2解题思路本题是01背包方案计数的经典应用题通过将等和划分问题转化为子集和计数问题使用动态规划高效求解。问题等价转化将 1~n 的整数集合划分为两个和相等的子集可按以下步骤推导计算全集总和s u m n ( n 1 ) 2 sum \frac{n(n1)}{2}sum2n(n1)​。若 sum 为奇数无法平分答案直接为 0。若 sum 为偶数设每个子集的目标和为t a r g e t s u m 2 target \frac{sum}{2}target2sum​。问题转化为从 1~n 中选出若干个数和恰好为 target求这样的子集总数。由于交换两个子集视为同一种划分方案最终答案等于子集总数除以 2。动态规划求解子集和计数采用01背包模型统计方案数状态定义dp[i][j]表示从前 i 个数中选取若干个和恰好为 j 的方案总数。初始边界dp[0][0] 1即不选任何数时和为 0 的方案有 1 种空集。状态转移对第 i 个数数值为 i有两种选择不选该数方案数继承自前 i-1 个数的结果即dp[i][j] dp[i-1][j]。选该数若 j ≥ i则加上前 i-1 个数和为 j-i 的方案数即dp[i][j] dp[i-1][j-i]。结果输出若总和为奇数直接输出 0。否则总子集方案数为dp[n][target]最终划分方案数为dp[n][target] / 2。算法时间复杂度为O ( n 2 ) O(n^2)O(n2)空间复杂度为O ( n 2 ) O(n^2)O(n2)n 最大为 39计算量极小完全满足题目要求。总结核心逻辑将等和划分问题转化为子集和计数问题通过01背包动态规划统计符合目标和的子集总数再除以2得到最终划分方案数。关键操作总和奇偶性预判、01背包方案计数递推、对称划分去重处理。效率保障n最大39总运算量仅千级运行开销极低。代码简要说明数组初始化a数组存储 1~n 的数值dp二维数组用于存储方案数全局数组默认初始化为 0手动设置dp[0][0] 1作为初始边界。DP递推外层遍历每个数字内层遍历所有可能的和按01背包规则更新方案数。奇偶判定若n*(n1)不能被 4 整除即总和为奇数直接输出 0否则输出dp[n][target]其中target n*(n1)/4。代码特性说明内层循环 j 从 1 开始未显式维护dp[i][0] 1因此仅统计了必须包含数字1的子集方案数。利用本题连续整数的数学性质目标和为总和一半时包含1的子集数恰好等于不包含1的子集数因此统计结果刚好等于总方案数的一半即最终答案。标准通用写法应从 j0 开始循环以维护空集方案最后将总方案数除以2逻辑更严谨且适用于任意数值集合。输入优化关闭流同步并解绑 tie提升输入输出效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cinn;ll a[45];for(ll i1;in;i)a[i]i;ll dp[45][2010]{};dp[0][0]1;for(ll i1;in;i)for(ll j1;jn*(n1)/2;j){dp[i][j]dp[i-1][j];if(ja[i])dp[i][j]dp[i-1][j-a[i]];}if(n*(n1)%40)coutdp[n][n*(n1)/4]endl;elsecout0endl;return0;}