【BZOJ1226】学校食堂Dining（状压DP）

题意：见题面

思路：设dp[i,sta,k]为前i个人已经吃完，从第i人到第i+b[i]人的吃饭状况是sta，前一个吃完的人离i的距离是k（可能为负）的最小值

[ dp[i+1,sta>>1,k-1]=min(dp[i+1,sta>>1,k-1],dp[i,sta,k]) (sta and 1=1，如果i已经吃完)]

[dp[i,sta+1<<l,l]=min(dp[i,sta+1<<l,l],dp[i,sta,k]+w(i+k,i+l) (第i+l人吃，前一个吃的人是i+k)]

[w(i,j)=b[i]  or  b[j]-b[i]  and  b[j]=b[i]  xor  b[j]]

注意转移的时候边界判断，是否超过l人里面最小的容忍范围

const oo=2000000000;
var dp:array[1..1100,0..300,-8..8]of longint;
    t,b:array[1..1100]of longint;
    cas,v,n,i,j,k,l,ans,r:longint;

function clac(x,y:longint):longint;
begin
 if x=0 then exit(0);
 exit(t[x] xor t[y]);
end;

function min(x,y:longint):longint;
begin
 if x<y then exit(x);
 exit(y);
end;

begin
 assign(input,'bzoj1226.in'); reset(input);
 assign(output,'bzoj1226.out'); rewrite(output);
 readln(cas);
 for v:=1 to cas do
 begin
  read(n);
  for i:=1 to n do read(t[i],b[i]);
  fillchar(dp,sizeof(dp),$7f);
  dp[1,0,-1]:=0;
  for i:=1 to n do
   for j:=0 to (1<<8)-1 do
    for k:=-8 to 7 do
     if dp[i,j,k]<oo then
     begin
      if j and 1>0 then
       dp[i+1,j>>1,k-1]:=min(dp[i+1,j>>1,k-1],dp[i,j,k])
        else
        begin
         r:=oo;
         for l:=0 to 7 do
          if j and (1<<l)=0 then
          begin
           if i+l>r then break;
           r:=min(r,i+b[i+l]+l);
           dp[i,j+(1<<l),l]:=min(dp[i,j+(1<<l),l],dp[i,j,k]+clac(i+k,i+l));
          end;
        end;
     end;
  ans:=oo;
  for i:=-8 to -1 do ans:=min(ans,dp[n+1,0,i]);
  writeln(ans);
 end;
 close(input);
 close(output);
end.