bzoj2064

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

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

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

不难发现,最少步骤=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.
上一篇:极值问题(acms)


下一篇:一步一步理解Paxos算法