这道题初看真的毫无思路，又是合并又是分裂的

但实际上我们知道，当两组和相等的时候才能由一组变成另一组

我们将初始状态和最终状态划分成若干对，每对中的两组元素和相等的

不难发现，最少步骤=n+m-2*对数

因为在一对不能再划分的组中，具有k个元素变换到具有j个元素所花的最短步骤是k+j-2

于是问题就转化为了怎么划分，划分的对数最多

由于n,m<=10,这样我们就可以把选取状况用01二进制表示来解决了；

我们先算出每个状态的每种组合情况的和

f[x,y]表示初始状态选取状况为x，最终状态选取状况为y的时候，最多划分成的对数

然后方便转移，我们可以采用记忆化搜索的方式

这道题题解不大好表达，只可意会不可言传

1 var w,f:array[0..1024,0..1024] of longint; 2     sum,a,b,c:array[0..1024] of longint; 3     n,m,i,j,s1,s2,s:longint; 4 function max(a,b:longint):longint; 5   begin 6     if a>b then exit(a) else exit(b); 7   end; 8  9 function dfs(x,y:longint):longint;10   var i,j,k:longint;11   begin12     if (x=s1) then13     begin14       if y<>s2 then exit(-1000)15       else exit(0);16     end;17     if (y=s2) then18     begin19       if s1=x then exit(0)20       else exit(-1000);21     end;22     if f[x,y]<>-1 then exit(f[x,y]);  //记忆化23     for i:=1 to s1 do24     begin25       if i and x=0 then26       begin27         k:=sum[i];28         for j:=1 to c[k] do   //在最终状态中找一个和初始状态的组合和相等的组形成新的一对29           if w[k,j] and y=0 then30             f[x,y]:=max(f[x,y],dfs(x xor i,y xor w[k,j])+1);31       end;32     end;33     exit(f[x,y]);34   end;35 36 begin37   read(n);38   for i:=1 to n do39     read(a[i]);40   read(m);41   for i:=1 to m do42     read(b[i]);43   s1:=1 shl n-1;44   s2:=1 shl m-1;45   for i:=0 to s1 do46     for j:=0 to n-1 do47       if i and (1 shl j)>0 then48         sum[i]:=sum[i]+a[j+1];49   for i:=0 to s2 do50   begin51     s:=0;52     for j:=0 to m-1 do53       if i and (1 shl j)>0 then54         s:=s+b[j+1];55     inc(c[s]);   //感觉这种做法很像Meet in middle56     w[s,c[s]]:=i;57   end;58   fillchar(f,sizeof(f),255);59   writeln(n+m-2*dfs(0,0));60 end.