题目
Description cza特别喜欢吃海苔，怎么吃也吃不够。cza的生日到来时，他的父母给他买了许许多多的海苔和一个生日蛋糕。海苔是一个1*2或2*1的长方形，而蛋糕则是一个n*m的矩阵。蛋糕上有一些蜡烛占据了位置，其他地方都可以放海苔。cza的父母让cza把海苔尽可能多的放在蛋糕上，但是海苔不能够重叠放置。cza想把海苔留着自己以后慢慢吃，可又不敢违背父母，于是他决定放一少部分在蛋糕上。为了不使父母起疑，cza必须确保放置完海苔后，蛋糕上不存在1*2或2*1的空白以放置更多的海苔。cza想知道这样得花多少海苔，请帮助他求出满足这样放置所需的最少海苔数。
Input 输入的第一行是蛋糕的规模n和m（注意是n行m列）
接下来的n行每一行含m个字符。每个字符要么是”.”，表示空白；要么是”*”，表示蜡烛。 Output 输出文件只包含一个整数k，表示满足题目要求的最小海苔数。
Sample Input 3 3
…
.*.
… Sample Output 3
Data Constraint 对于30%的数据N<=5，M<=5 对于100%的数据N<=70， M<=7
思路
这道题比较有难度。 用状压DP，只需要考虑一个格子中有或没有海苔/蜡烛。
DP，设F[i,s1,s2]表示第i行状态为s1，第i+1行状态为s2。 则每次枚举两行状态，根据第i-1行状态判断，通过dfs填充第i行空缺，顺便填一部分第i+1行。
分三种情况讨论。 ① 当前位置不放。 条件就是上一格和左一个不能有空缺（如果空缺就会有1*2的空隙，并且不能在下一行补回）。 或者当前这一格有东西（放不下）。
②水平放置。 有地方放就可以放。
③垂直放置。 同上。
代码
var
a:
array[
1..
71]
of longint;
f:
array[
0..
71,
0..
127,
0..
127]
of longint;
g:
array[
0..
127]
of boolean;
n,m,i,j,k,l,ans,ll:longint;
ch:char;
procedure init(t,s,l:longint);
begin
if t>m
then
begin
g[s]:=
true;
exit;
end;
if l=
1 then
init(t+
1,s*
2,
0);
init(t+
1,s*
2+
1,
1);
end;
function min(x,y:longint):longint;
begin
if x<y
then min:=x
else
min:=y;
end;
procedure dfs(t,x,y,z,s:longint);
begin
if t>ll
then
begin
f[i,y,z]:=min(f[i,y,z],f[i-
1,j,k]+s);
exit;
end;
if ((x
and t>
0)
and ((t=
1)
or ((y
and (t
div 2))>
0)))
or (y
and t>
0)
then
dfs(t*
2,x,y,z,s);
if (y
and t=
0)
and (z
and t=
0)
then
dfs(t*
2,x,y+t,z+t,s+
1);
if (t*
2<ll)
and (y
and t=
0)
and (y
and (t*
2)=
0)
then
dfs(t*
2,x,y+t*
3,z,s+
1);
end;
begin
assign(Input,
'cake.in'); reset(Input);
assign(Output,
'cake.out'); rewrite(Output);
readln(n,m);
ll:=(
1 shl m)-
1;
init(
1,
0,
1);
for i:=
1 to n
do
begin
for j:=
1 to m
do
begin
read(ch);
a[i]:=a[i]*
2;
if ch=
'*' then
inc(a[i]);
end;
readln;
end;
fillchar(f,sizeof(f),$
7F);
f[
0,ll,a[
1]]:=
0;
for i:=
1 to n
do
begin
for j:=
0 to ll
do
if g[j]=
true then
begin
for k:=
0 to ll
do
if f[i-
1,j,k]<
2000000000 then
dfs(
1,j,k,a[i+
1],
0);
end;
end;
ans:=maxlongint;
for i:=
0 to ll
do
ans:=min(ans,f[n,i,
0]);
writeln(ans);
close(Input); close(Output);
end.
