SGU 132 Another Chocolate Maniac 状压DP

    一块N*M的蛋糕，有些位置空着，有些位置放着蜡烛，可以用1*2,2*1的巧克力来覆盖空位，问最少需要多少块巧克力，可是使蛋糕上不存在空着的1*2或2*1的区域..蛋糕的宽度最大只有7，可以状压来做。因为放巧克力时，只有当前层和下一层的状态会有影响，所以可以同滚动数组来存储状态每次扩展的时候，先判断一下当前层和上一层是否存在非法的状态(存在完整的1*2或2*1的区间)，然后dfs扩展本层所有可以放置巧克力的情况..枚举完一层后，更新一下这一层的最小值。算结果时，因为最后一层的下一层是不能放巧克力的，所以遍历状态sta，在dp[n&1][sta][0]中找到最小值输出即可.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int inf=1<<29;
int ocp[77];
char s[10];
int n,m;
int f[2][1<<9][1<<9];
int sta;
int tmps1,tmps2;
int i;

bool AND(int a,int b)
{
    return a&b;
}
void dfs(int pos,int s1,int s2,int cp,int cnt)
{
    if (pos>0 && AND(s1,1<<(pos-1))==0 && AND(s2,1<<(pos-1))==0) return;
    if (pos>1 && AND(s2,1<<(pos-1))==0 && AND(s2,1<<(pos-2))==0) return;

    if (pos==m)
    {
        f[i&1][s2][cp]=min(f[i&1][s2][cp],f[1-(i&1)][tmps1][tmps2]+cnt);
        return;
    }
    dfs(pos+1,s1,s2,cp,cnt);

    if (pos<m-1 && AND(s2,1<<pos)==0 && AND(s2,1<<(pos+1))==0)
    dfs(pos+1,s1,s2|(1<<pos)|(1<<(pos+1)),cp,cnt+1);

    if ( AND(s2,1<<(pos))==0 && AND(cp,1<<pos)==0)
    dfs(pos+1,s1,s2|(1<<pos),cp|(1<<pos),cnt+1);
}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    memset(ocp,0,sizeof ocp);
    for (int i=1; i<=n; i++)
    {
        scanf("%s",s);
        for (int j=0; j<m; j++)
        if (s[j]=='*') ocp[i]|=(1<<j);
    }
    sta=(1<<m);
    memset(f,0x3f3f,sizeof f);
    f[0][sta-1][ocp[1]]=0;
    for (i=1; i<=n; i++)
    {
     memset(f[i&1],0x3f3f,sizeof f[i&1]);
     for (int s1=0; s1<sta; s1++)
     for (int s2=0; s2<sta; s2++)
     {
         if (f[1-(i&1)][s1][s2]<inf)
         {
             tmps1=s1;
             tmps2=s2;
             dfs(0,s1,s2,ocp[i+1],0);
         }
     }
    }
    int ans=inf;
    for (int i=0; i<sta; i++)
    ans=min(ans,f[n&1][i][0]);
    cout<<ans<<endl;
    return 0;
}