BZOJ 2060
题意：一个初始集合($n$个元素)和一个目标集合($m$个元素)($1 \leq n,m \leq 10$)，两个操作
- 操作$1$将集合里的两个数合成一个数
- 操作$2$将集合的一个数分成两个数
问对初始集合最少进行几次操作可以到达目标集合
显然最多的次数就是将初始集合全部合成一个数然后再分成目标集合，也就是次数上界为$n+m-2$
把初始集合和目标集合分成尽量多的子集让这些子集都能对应(子集元素和相等)，如果能分成$x$个子集，那么次数就是$n+m-2x$
考虑设$dp(S_1,S_2)$为把$S_1$和$S_2$最多能分成几个能相对应的子集(子集元素和相等)。则
$$
dp(S_1,S_2)=\max(dp(S_1 - k,S_2), dp(S_1,S_2 - k))
$$
若$\operatorname{sum}(S_1)=\operatorname{sum}(S_1)$，则$dp(S_1,S_2)+=1$
因为不相同时不能用上所有的，相同时加减掉一个元素一定少一个集合
知识点
1、集合DP思想
2、$\operatorname{lowbit}$来快速枚举子串，用于合并答案的递推非常好用(看代码)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int n, m;
int sum1[1030], sum2[1030];
int dp[1030][1030];
int lowbit(int x) {return x & (-x);}
void clean() {
ms(sum1, 0), ms(sum2, 0), ms(dp, 0);
}
int solve() {
clean();
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &sum1[1 << i]);
scanf("%d", &m);
for (int i = 0; i < m; ++i) scanf("%d", &sum2[1 << i]);
for (int i = 1; i < (1 << n); ++i) sum1[i] = sum1[lowbit(i)] + sum1[i ^ lowbit(i)];
for (int i = 1; i < (1 << m); ++i) sum2[i] = sum2[lowbit(i)] + sum2[i ^ lowbit(i)]; // lowbit 求集合和
for (int i = 1; i < (1 << n); ++i) {
for (int j = 1; j < (1 << m); ++j) {
for (int k = 0; k < max(n, m); ++k) {
if ((1 << k) & i) dp[i][j] = max(dp[i][j], dp[i ^ (1 << k)][j]);
if ((1 << k) & j) dp[i][j] = max(dp[i][j], dp[i][j ^ (1 << k)]);
}
if (sum1[i] == sum2[j]) ++dp[i][j];
}
}
printf("%d\n", n + m - 2 * dp[(1 << n) - 1][(1 << m) - 1]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
