Description：

给出一个起始集合和一个终止集合，每次可以合并或者分裂两个集合，要求前后和相等，问最少操作次数。

$1\leqslant n\leqslant 10$

Solution：

首先发现操作的下限是 $n+m-2$ ，即把所有的先都合起来，然后再都分开。

然后一个重要的模型转化是发现如果起始集合的一个子集和一个终止集合的子集和相同，那他们就可以不用和其他的合在一起，这样可以省掉两个操作，因此总方案数为： $n+m-2-$ 这样的子集对数 $\times2$ ，问题就变成了怎么求这样的对数，可以设 $f[i][j]$ 表示起始集合选了 $i$ ，终止集合选了 $j$ ，最多能有多少个这样的子集对数，这样可以枚举子集来转移，但时间复杂度承受不住，但是发现如果在一个序列上，值有正有负，那么如果随机一个序列有最多的前缀和为 $0$ 的点，那么就有这么多个子集和为 $0$ ，于是可以按一定顺序依次加入两个集合的数，预处理集合的和，如果 $sa[i]=sb[j]$ ，就说明找到了一个前缀和为 $0$ 的位置，这样就可以 $DP$ 了，即 $f[i][j]$ 表示集合 $A$ 选了 $i$ ，集合 $B$ 选了 $j$ ，如果 $sa[i]=sb[j]$ 就加一，每次选一个 $A$ 集合中的或者 $B$ 集合中的增量，注意要减掉 $0$ 和 $sum$ 这两个不会产生贡献的情况。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 11

int a[MAXN],b[MAXN];

int sa[1 << MAXN],sb[1 << MAXN];

int f[1 << MAXN][1 << MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 0;i < (1 << n);++i)

		for(int j = 1;j <= n;++j)

			if(i & (1 << (j - 1)))sa[i] += a[j];

	scanf("%d",&m);

	for(int i = 1;i <= m;++i)scanf("%d",&b[i]);

	for(int i = 0;i < (1 << m);++i)

		for(int j = 1;j <= m;++j)

			if(i & (1 << (j - 1)))sb[i] += b[j];

	for(int i = 0;i < (1 << n);++i)

	{

		for(int j = 0;j < (1 << m);++j)

		{

			for(int x = 1;x <= n;++x)

				if(i & (1 << (x - 1)))f[i][j] = max(f[i][j],f[i ^ (1 << (x - 1))][j]);

			for(int y = 1;y <= m;++y)

				if(j & (1 << (y - 1)))f[i][j] = max(f[i][j],f[i][j ^ (1 << (y - 1))]);

			f[i][j] += (sa[i] == sb[j]) * 2;

		}

	}

	cout << (n + m - 2) - (f[(1 << n) - 1][(1 << m) - 1] - 4) << endl;

	return 0;

}