【题意】
有个N*M个格子芯片,其上有k个坏点,问放2*3的组件最多能放多少个
N (1 <= N <= 150), M (1 <= M <= 10)
【输入】
第一行是个D,表示多少组数据
第二N,M,K
然后K行描述哪几个点坏了
【输出】
每组数据输出一个数,表示最多能放多少个。
有个N*M个格子芯片,其上有k个坏点,问放2*3的组件最多能放多少个
N (1 <= N <= 150), M (1 <= M <= 10)
【输入】
第一行是个D,表示多少组数据
第二N,M,K
然后K行描述哪几个点坏了
【输出】
每组数据输出一个数,表示最多能放多少个。
M很小,所以每行可以状压表示
状态压缩压两行
3进制表示
0表示都没有
1表示第一行有
2表示第二行有
明白算法以后还是很好写的
=、=最大的错误是y+3写成了y+4
还有一个错误对于之前的不同状态递推过来的的dp要重新做一遍
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; read(d); for l:=1 to d do begin fillchar(yes,sizeof(yes),false); read(n,m,k); for i:=1 to k do begin read(x,y); 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.