题解 UVA1381 【Balancing the Scale】

2019-08-27 14:25:51


$\text{meet in the middle}$ 。

枚举 $4$ 个数 $a_1,a_2,a_3,a_4$ ,设 $w=a_1+2a_2+3a_3+4a_4$ 。

对于每一种 $w$ 开一个 vector ,记下所有权值为 $w$ 的四元组。

对于当前的 $w$ ,到对应的 vector 中遍历所有四元组,如果两个四元组没有交就说明这八个数可以放在算式里。

设 $cnt_S$ 表示八元组 $S$ 有多少种方法放在算式里。这个在上面那句话时处理出来。

然后只需要枚举所有八元组 $S$ ,设另外八个数组成的八元组为 $T$ ,那么把 $cnt_S\times cnt_T$ 加到答案里去。

这样子会多算一遍,所以最后还要除以二。

代码中四元组、八元组可以用状压实现。