这道题初看真的毫无思路,又是合并又是分裂的
但实际上我们知道,当两组和相等的时候才能由一组变成另一组
我们将初始状态和最终状态划分成若干对,每对中的两组元素和相等的
不难发现,最少步骤=n+m-2*对数
因为在一对不能再划分的组中,具有k个元素变换到具有j个元素所花的最短步骤是k+j-2
于是问题就转化为了怎么划分,划分的对数最多
由于n,m<=10,这样我们就可以把选取状况用01二进制表示来解决了;
我们先算出每个状态的每种组合情况的和
f[x,y]表示初始状态选取状况为x,最终状态选取状况为y的时候,最多划分成的对数
然后方便转移,我们可以采用记忆化搜索的方式
这道题题解不大好表达,只可意会不可言传
var w,f:array[..,..] of longint;
sum,a,b,c:array[..] of longint;
n,m,i,j,s1,s2,s:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; function dfs(x,y:longint):longint;
var i,j,k:longint;
begin
if (x=s1) then
begin
if y<>s2 then exit(-)
else exit();
end;
if (y=s2) then
begin
if s1=x then exit()
else exit(-);
end;
if f[x,y]<>- then exit(f[x,y]); //记忆化
for i:= to s1 do
begin
if i and x= then
begin
k:=sum[i];
for j:= to c[k] do //在最终状态中找一个和初始状态的组合和相等的组形成新的一对
if w[k,j] and y= then
f[x,y]:=max(f[x,y],dfs(x xor i,y xor w[k,j])+);
end;
end;
exit(f[x,y]);
end; begin
read(n);
for i:= to n do
read(a[i]);
read(m);
for i:= to m do
read(b[i]);
s1:= shl n-;
s2:= shl m-;
for i:= to s1 do
for j:= to n- do
if i and ( shl j)> then
sum[i]:=sum[i]+a[j+];
for i:= to s2 do
begin
s:=;
for j:= to m- do
if i and ( shl j)> then
s:=s+b[j+];
inc(c[s]); //感觉这种做法很像Meet in middle
w[s,c[s]]:=i;
end;
fillchar(f,sizeof(f),);
writeln(n+m-*dfs(,));
end.