考虑最坏的做法，就是将所有集合合并起来再拆开，需要n+m-2次
当两个的某一个子集和相同时，这个子集和单独处理，不与整体合并，可以减少2次
那么题目转化为询问有最多能选出多少个不相交的子集对，满足子集和相同
状压dp，用f[S1][S2]表示从S1和S2中选，那么分为两种情况考虑：
1.S1的和等于S2的和，这时候最终的选出来的集合的并集应该就是全集，又因为不相交，所以任意去掉一个元素的dp状态+1即可
2.S1的和不等于S2的和，这时候枚举去掉的元素取max即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,a[15],b[15],sa[2005],sb[2005],f[2005][2005]; 4 int low(int k){ 5 return k-(k&(k-1)); 6 } 7 int main(){ 8 scanf("%d",&n); 9 for(int i=0;i<n;i++)scanf("%d",&sa[1<<i]); 10 scanf("%d",&m); 11 for(int i=0;i<m;i++)scanf("%d",&sb[1<<i]); 12 for(int i=1;i<(1<<n);i++)sa[i]=sa[low(i)]+sa[i-low(i)]; 13 for(int i=1;i<(1<<m);i++)sb[i]=sb[low(i)]+sb[i-low(i)]; 14 for(int i=1;i<(1<<n);i++) 15 for(int j=1;j<(1<<m);j++) 16 if (sa[i]==sb[j])f[i][j]=f[i-low(i)][j]+1; 17 else{ 18 for(int k=0;k<n;k++) 19 if (i&(1<<k))f[i][j]=max(f[i][j],f[i-(1<<k)][j]); 20 for(int k=0;k<m;k++) 21 if (j&(1<<k))f[i][j]=max(f[i][j],f[i][j-(1<<k)]); 22 } 23 printf("%d",n+m-2*f[(1<<n)-1][(1<<m)-1]); 24 }
原文：https://www.cnblogs.com/PYWBKTDA/p/11833578.html
