[COGS 301][NOI 2001]砲兵陣地

トランスファゲート
http://cojs.tk/cogs/problem/problem.php?pid=301
テーマの大意
指定の01碁盤、1は砲兵を放すことができて、各砲兵の間のxとy軸の距離は2以上で、質問は最大でいくつ放すことができます
問題解
状圧DPは[BZOJ 1725][Usaco 2006 Nov]Corn Fields牧場の手配によって類似の状態(その問題は1ビット離れており、これは2ビット離れている)dp[i,j,k]:i行目の状態がjであり、i−1行目の状態がk dp[i,j,k]=max(dp[i−1,k,l]+sum[j],dp[i,j,k])であることを示す.

var
 x:array[0..200,0..20]of longint;
 sum,y:array[0..200]of longint;
 z:array[0..200,0..100]of longint;
 dp:array[0..200,0..200,0..200]of longint;
 i,j,k,l:longint;
 n,m,t,ans:longint;
 cha:char;
function max(a,b:longint):longint;
begin
 if a>b then exit(a) else exit(b);
end;

procedure prepare;
var a,b,c,d,summ:longint;
begin
 t:=1;
 for i:=0 to (1<<m)-1 do
  begin
   l:=1; summ:=0;
   for j:=1 to m do
    begin
     a:=0; b:=0; c:=0; d:=0;
     if i and(1<<(j-1))=0 then continue else inc(summ);
     if j-1>0 then a:=i and(1<<(j-2));
     if j-2>0 then b:=i and(1<<(j-3));
     if j+1<=m then c:=i and(1<<(j));
     if j+2<=m then d:=i and(1<<(j+1));
     if (a<>0)or(b<>0)or(c<>0)or(d<>0) then begin l:=0; break; end;
    end;
   if l=1 then begin y[t]:=i; sum[t]:=summ; inc(t); end;
  end;
 dec(t);
 for i:=1 to n do
  for j:=1 to t do
   begin
    z[i,j]:=1;
    for k:=1 to m do
     if (y[j] and(1<<(k-1))<>0)and(x[i,k]=0)
     then begin z[i,j]:=0; break; end;
   end;
 for j:=1 to t do
  for k:=1 to t do
   if (z[2,j]=1)and(z[1,k]=1)and(y[j]and y[k]=0)
   then dp[2,j,k]:=sum[j]+sum[k];
end;

begin
 readln(n,m);
 for i:=1 to n do
  begin
   for j:=1 to m do
    begin read(cha); if cha='P' then x[i,j]:=1 else x[i,j]:=0; end;
   readln;
  end;
 prepare;
 for i:=3 to n do
  for j:=1 to t do
   if z[i,j]=1 then
   for k:=1 to t do
    if z[i-1,k]=1 then
    for l:=1 to t do
     if (z[i-2,l]=1)and(y[l] and y[k]=0)and((y[l] or y[k])and y[j]=0)
     then dp[i,j,k]:=max(dp[i,j,k],dp[i-1,k,l]+sum[j]);
 ans:=0;
 for i:=1 to t do
  for j:=1 to t do
   ans:=max(ans,dp[n,i,j]);
 writeln(ans);
end.