[SGU]132. Another Chocolate Maniac

Analysis

    还是一道状态压缩题目，与SGU131不同的是，一个要填满，一个不用，这样一来此题中上一行的状态将会影响到当前行，故应在状态表示时记录两行。设f[i,opt1,opt2]是当前为第i行，上一行状态为opt1，当前行状态为opt2时的方案总数，用与前一题相似的方法推到下一个状态。

Accepted Code

var
    f:array[0..1,0..200,0..200] of int64;
    a:array[1..100] of longint;
    i,j,l,m,n,ans,maxopt:longint;
    s:string;

function min(i,j:longint):longint;
begin
    if i<j then
        min:=i
    else
        min:=j;
end;

procedure dfs(k,opt1,opt2,opt3,cnt:longint);
begin
    if (k>0) and (opt1 and (1 shl (k-1))=0) and (opt2 and (1 shl (k-1))=0) then
        exit;
    if (k>1) and (opt2 and (1 shl (k-1))=0) and (opt2 and (1 shl (k-2))=0) then
        exit;
    if k=n then
    begin
        f[i and 1,opt2,opt3]:=min(f[i and 1,opt2,opt3],f[1-i and 1,j,l]+cnt);
        exit;
    end;
    dfs(k+1,opt1,opt2,opt3,cnt);
    if (opt3 and (1 shl k)=0) and (opt2 and (1 shl k)=0) then
        dfs(k+1,opt1,opt2 or (1 shl k),opt3 or (1 shl k),cnt+1);
    if (k<n-1) and (opt2 and (1 shl (k+1))=0) and (opt2 and (1 shl k)=0) then
        dfs(k+2,opt1,opt2 or (1 shl k) or (1 shl (k+1)),opt3,cnt+1);
end;

begin
    readln(m,n);
    for i:=1 to m do
    begin
        readln(s);
        a[i]:=0;
        for j:=1 to n do
            if s[j]='*' then
                a[i]:=a[i] or (1 shl (j-1));
    end;
    maxopt:=1 shl n-1;
    for j:=0 to maxopt do
        for l:=0 to maxopt do
            f[0,j,l]:=maxlongint div 2;
    f[0,maxopt,a[1]]:=0;
    for i:=1 to m do
    begin
        for j:=0 to maxopt do
            for l:=0 to maxopt do
                f[i and 1,j,l]:=maxlongint div 2;
        for j:=0 to maxopt do
            for l:=0 to maxopt do
                if f[1-i and 1,j,l]<>maxlongint div 2 then
                    dfs(0,j,l,a[i+1],0);
    end;
    ans:=maxlongint div 2;
    for i:=0 to maxopt do
        ans:=min(ans,f[m and 1,i,0]);
    writeln(ans);
end.