搜索 此题数据小，不需要状压

Program P1856;
var
   n,m,i,j,ans:longint;
   c:char;
   f:array[0..1010,0..1010] of boolean;
function find(x,y:longint):boolean;
var
   i,j,k,l:longint;
begin
   i:=x;j:=y;
   while f[x,j] do inc(j);
   dec(j);
   while f[i,y] do inc(i);
   dec(i);
   for k:=x to i do
      for l:=y to j do
      begin
         if not(f[k,l]) then exit(false);
         f[k,l]:=false;

      end;
   for k:=x-1 to i+1 do
      if f[k,j+1] or f[k,y-1] then exit(false);
   for l:=y to j do
      if f[i+1,l] or f[x-1,l] then exit(false);




   exit(true);



end;
function main:boolean;
var
   i,j:longint;
begin
   ans:=0;
   for i:=1 to n do
      for j:=1 to m do
         if f[i,j] then
         begin
            if not(find(i,j)) then exit(false)
            else inc(ans);
         end;

   exit(true);
end;
begin
   while not seekeof do
   begin
      fillchar(f,sizeof(f),false);
      readln(n,m);
      if (n+m=0) then break;
      for i:=1 to n do
      begin
         for j:=1 to m do
         begin
            read(c);
            if c='#' then f[i,j]:=true;

         end;
         readln;
      end;

      if main then writeln('There are ',ans,' ships.')
      else writeln('Bad placement.');
   end;
end.

注意sum的改变

共2^20种情况，应该也可以用位运算

Program P2531;
Var
   n,i,j:longint;
   a:array[1..20,1..20] of longint;
   b:array[1..20] of boolean;
   ans:longint;
procedure dfs(k,sum:longint);
var
   i,j,sum2:longint;
begin
   b[k]:=true;
   sum2:=sum;
   for i:=1 to n do
      if b[i] then dec(sum2,a[i,k])
      else inc(sum2,a[i,k]);
   if (ans<sum2) then ans:=sum2;
   for i:=k+1 to n do
   begin
      dfs(i,sum2);
   end;

   b[k]:=false;
end;
begin
   ans:=-100000;
   read(n);
   fillchar(b,sizeof(b),false);
   for i:=1 to n do
      for j:=1 to n do
         read(a[i,j]);
   dfs(1,0);
   writeln(ans);
end.