## poj1038

2018年01月15日 ⁄ 综合 ⁄ 共 1707字 ⁄ 字号 评论关闭
【题意】

N (1 <= N <= 150), M (1 <= M <= 10)
【输入】

【输出】

M很小，所以每行可以状压表示

3进制表示
0表示都没有
1表示第一行有
2表示第二行有

=、=最大的错误是y+3写成了y+4

```program poj1038;
type
bas=array [0..11] of longint;
var
n,m,i,j,k,x,y,l,d,o,r,ans:longint;
yes:array [0..151,0..11] of boolean;
f:array [0..1,0..59049] of longint;
three:array [0..11] of longint;
q,p:bas;
function max (a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
function hash (q:bas):longint;
var
i,ans:longint;
begin
ans:=0;
for i:=1 to m do
ans:=ans+three[i-1]*q[i];
exit(ans);
end;
function rehash (r:longint):bas;
var
i:longint;
begin
fillchar(rehash,sizeof(rehash),0);
for i:=1 to m do
begin
rehash[i]:=r mod 3;
r:=r div 3;
end;
end;
procedure dfs (now,y,r:longint);
var
i:longint;
begin
if now>ans then ans:=now;
if (y+1<=m)and(q[y]=0)and(q[y+1]=0)and(p[y]=0)and(p[y+1]=0) then
begin
p[y]:=2;
p[y+1]:=2;
i:=hash(p);
if now+1>f[o,i] then f[o,i]:=now+1;
dfs(now+1,y+2,i);
p[y]:=0;
p[y+1]:=0;
end;
if (y+2<=m)and(p[y]=0)and(p[y+1]=0)and(p[y+2]=0) then
begin
p[y]:=2;
p[y+1]:=2;
p[y+2]:=2;
i:=hash(p);
if now+1>f[o,i] then f[o,i]:=now+1;
dfs(now+1,y+3,i);
p[y]:=0;
p[y+1]:=0;
p[y+2]:=0;
end;
if now>f[o,r] then f[o,r]:=now;
if (y+1<=m) then dfs(now,y+1,r);
end;
begin
three[0]:=1;
for i:=1 to 11 do
three[i]:=three[i-1]*3;
for l:=1 to d do
begin
fillchar(yes,sizeof(yes),false);
for i:=1 to k do
begin
yes[x,y]:=true;
end;
for i:=1 to m do
if yes[1,i] then q[i]:=2
else q[i]:=1;
o:=0;
fillchar(f,sizeof(f),255);
r:=hash(q);
f[o,r]:=0;
ans:=0;
for i:=2 to n do
begin
o:=1-o;
fillchar(f[o],sizeof(f[o]),255);
for j:=0 to three[m]-1 do
if f[1-o,j]<>-1 then
begin
q:=rehash(j);
for k:=1 to m do
if yes[i,k] then p[k]:=2
else
if q[k]<2 then p[k]:=0
else p[k]:=1;
r:=hash(p);
dfs(f[1-o,j],1,r);
end;
end;
writeln(ans);
end;
end.```
【上篇】
【下篇】