P1566 加等式网页链接P1566 加等式题目描述对于一个整数集合我们定义“加等式”如下集合中的某一个元素可以表示成集合内其他元素之和。如集合1 , 2 , 3 {1,2,3}1,2,3中就有一个加等式3 1 2 312312。而且3 1 2 312312和3 2 1 321321是相同的加等式也是这个集合唯一的加等式。给定一个整数集合编程找出其加等式的个数。输入格式第一行为t tt表示测试数据组数。接下来t tt行每行表示一组测试数据。其中第一个数m mm表示集合元素的个数接下来m mm个不同的整数x i x_ixi表示集合元素。输出格式对于每个输入数据输出一个整数表示其中加等式的个数。输入输出样例 #1输入 #13 3 1 2 3 3 1 2 5 6 1 2 3 5 4 6输出 #11 0 7说明/提示1 ≤ t ≤ 10 1\le t\le 101≤t≤101 ≤ m ≤ 30 1\le m \le 301≤m≤301 ≤ x ≤ 1000 1\le x\le 10001≤x≤1000。解题思路本题要求统计一个集合中“加等式”的数量即存在一个元素等于集合中其他元素之和。由于数据规模较小m ≤ 30 m\le 30m≤30元素值≤ 1000 \le 1000≤1000可以采用子集和 DP的思想先将元素排序然后依次枚举每个元素作为“和”利用背包 DP 统计用前面较小的元素组成该数的方案数并累加答案。1. 问题等价转化加等式定义集合中某个元素x xx可以表示为集合中若干个其他元素之和。注意“其他元素”不能包含x xx自身且组合不考虑顺序即{ a , b } \{a,b\}{a,b}与{ b , a } \{b,a\}{b,a}视为同一种。计数策略将元素从小到大排序依次考虑每个元素a i a_iai。此时所有可能参与求和组成a i a_iai的元素一定来自a 1 ∼ a i − 1 a_1 \sim a_{i-1}a1∼ai−1严格小于a i a_iai。如果我们能计算出用前i − 1 i-1i−1个元素组成和为a i a_iai的不同子集个数那么这些方案就对应以a i a_iai为“和”的加等式。子集和 DP维护一个数组f [ v ] f[v]f[v]表示当前已考虑的元素中选出若干元素每个最多一次其和恰好为v vv的方案数。顺序扫描元素对于当前元素a i a_iaif [ a i ] f[a_i]f[ai]即为组成a i a_iai的加等式个数由前面的元素构成。累加后再将a i a_iai加入 DP 的候选集合中更新f ff供后续更大的元素使用。2. 算法实现排序 背包 DP输入与排序读取集合大小m mm和所有元素计算元素总和s u m sumsum用于 DP 上限。将元素按升序排序保证前面元素总是小于后面的。DP 初始化f [ 0 ] 1 f[0]1f[0]1其余为0 00表示空集和为0 00的方案数为1 11。遍历元素i 1 ∼ m i 1 \sim mi1∼m累加答案a n s f [ a i ] ans \mathrel{} f[a_i]ansf[ai]。此时f ff仅由a 1 ∼ a i − 1 a_1 \sim a_{i-1}a1∼ai−1更新过因此f [ a i ] f[a_i]f[ai]恰好是用严格小于a i a_iai的元素组成a i a_iai的方案数。更新 DP将当前元素a i a_iai加入背包。为防止同一个元素被重复使用需倒序更新for j sum down to a_i: f[j] f[j - a_i]。输出答案每组数据处理完后输出a n s ansans。3. 复杂度分析时间复杂度每组数据需要进行m mm次 DP 更新每次更新规模为O ( s u m ) O(sum)O(sum)。m ≤ 30 m \le 30m≤30s u m ≤ 30 × 1000 30000 sum \le 30 \times 1000 30000sum≤30×100030000单组复杂度约9 × 10 5 9 \times 10^59×105。共t ≤ 10 t \le 10t≤10组总操作量不到10 7 10^7107轻松通过。空间复杂度O ( s u m ) O(sum)O(sum)用于 DP 数组s u m sumsum最大30000 3000030000空间极小。总结巧妙地将“加等式”计数转化为有序子集和问题排序后每个元素作为和时其组合只能来自更小的元素通过背包 DP 统计组合方案数。先统计答案再更新 DP 的方式确保了当前元素不会被自己用来组合自己。该方法简洁高效完美契合数据范围。代码简要说明输入处理读入t tt对每组数据读入m mm和数组a aa计算总和s u m sumsum并对a aa排序。DP 数组f[30010]存储组合方案数初始f[0]1。核心循环遍历排序后的a i a_iai先将f[a[i]]加入答案然后倒序更新ff[j] f[j - a[i]]j jj从s u m sumsum降到a i a_iai。输出输出ans每组数据后换行。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll t,m;ll a[40];ll f[30010];ll sum;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cint;while(t--){cinm;sum0;for(ll i1;im;i){cina[i];suma[i];}sort(a1,am1);memset(f,0,sizeof(f));f[0]1;ll ans0;for(ll i1;im;i){ansf[a[i]];for(ll jsum;ja[i];j--)f[j]f[j-a[i]];}coutansendl;}return0;}