请问这道题有没有非状态压缩做法？

陈学威 @ 2018-10-22 14:53:46

by ljc20020730 @ 2018-10-22 14:54:59

你说呢？@陈学威

uses math;
var n,m,i,j,r1,r2,ans,cnt:longint;
    f:array[0..100,0..100,0..100]of longint;
    //f[i,j,k]表示当前第i行状态为j，i-1行状态为k的炮兵数
    s:string;
    st,sum,col:array[0..100]of longint;
function pd(x:longint):boolean;//判断此时放的是否合法（附近两位不能有1）
begin
 if (x and (x<<1))<>0 then exit(false);
 if (x and (x<<2))<>0 then exit(false);
 exit(true);
end;
function getbit(x:longint):longint;//求出二进制数x中有几个1
var sum:longint;
begin
 sum:=0;
 while x>0 do begin
  if (x and 1)=1 then inc(sum);
  x:=x>>1;
 end;
 exit(sum);
end;
procedure getdp(m:longint);
var e,i:longint;
begin
 e:=1<<m;
 cnt:=0;
 for i:=0 to e-1 do
  if pd(i) then begin
   inc(cnt);
   st[cnt]:=i; //保存此时的状态
   sum[cnt]:=getbit(i); //炮兵的个数
  end;
end;
begin
 readln(n,m);
 getdp(m);
 fillchar(col,sizeof(col),0);
 for i:=1 to m do col[0]:=col[0] or (1<<i);
 for i:=1 to n do begin
  readln(s);
  for j:=1 to m do
   if s[j]='H' then col[i]:=col[i] or (1<<(j-1));
 end;
 //col[i]表示第i行高地的分布
 fillchar(f,sizeof(f),255);//clear!
 for i:=1 to cnt do begin
  if (col[1] and st[i])=0 then f[1,1,i]:=sum[i];
 end;
 for i:=2 to n do
 for j:=1 to cnt do  //现在这行的状态是j
  if (col[i] and st[j])=0 then
   for r1:=1 to cnt do //上一行状态是r1
   if (st[j] and st[r1])=0 then
    for r2:=1 to cnt do //上上行的状态是r2
    if (st[j] and st[r2])=0 then
     if f[i-1,r2,r1]<>-1 then
      f[i,r1,j]:=max(f[i,r1,j],f[i-1,r2,r1]+sum[j]);
 ans:=0;
 for i:=1 to cnt do
  for j:=1 to cnt do
   ans:=max(ans,f[n,i,j]);
 writeln(ans);
end.

by King_of_gamers @ 2018-10-22 14:55:17

你强任你强,东皇加张良

by ljc20020730 @ 2018-10-22 14:55:39

线段树优化（滑稽） ?

by King_of_gamers @ 2018-10-22 14:56:05

感觉这状态是错的??

by 陈学威 @ 2018-10-22 14:56:13

@炜哥
啊????

by 陈学威 @ 2018-10-22 14:57:09

@炜哥
我觉得，就是f[i][j]要把边上所有可能覆盖的地方继承过来，所以就有点不会了

by King_of_gamers @ 2018-10-22 14:57:16

不知道,我不会啊

by Everlasting_Snow @ 2018-10-22 14:57:35

炜哥日常装弱

by Hope2075 @ 2018-10-22 15:13:47

搜索是非状压做法

by March_H @ 2018-10-22 15:18:11

相较搜索，状压效率更高吧？