SGU 132 Another Chocolate Maniac

题目：http://acm.sgu.ru/problem.php?contest=0&problem=132

题意：在一个n*m的蛋糕上，放1*2的巧克力条，使得最后只存在1*1的空格，求最小要放几个巧克力条

 

设dp[i][j][k]   i 表示第几行，j 表示当前行的状态，k 表示下一行的状态

然后根据上一行的状态来推当前行和下一行的状态

填充时应该往后填，因为不填后再往前填等于没有空出来

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m;
char s[80][10];
int a[80];
int dp[2][1<<8][1<<8];
void dfs(int last,int now,int nextt,int l,int k,int cnt)
{
    if (l==m)
    {
        dp[k][now][nextt]=min(dp[k][now][nextt],cnt);
        return;
    }
    if (now>>l&1) dfs(last,now,nextt,l+1,k,cnt);
    else
    {
        int t=now|1<<l;
        if (l+1<m&&!(now&1<<(l+1)))
            dfs(last,t|1<<(l+1),nextt,l+1,k,cnt+1);
        if (!(nextt&1<<l))
            dfs(last,t,nextt|1<<l,l+1,k,cnt+1);
        if (last>>l&1)
        {
            if (l==0||now>>(l-1)&1)
                dfs(last,now,nextt,l+1,k,cnt);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    {
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++)
        {
            scanf("%s",s[i]);
            for(int j=0;j<m;j++)
                if (s[i][j]=='*') a[i]|=1<<j;
        }
        int tot=1<<m;
        int now=0,pre=1;
        memset(dp[now],0x3f,sizeof(dp[now]));
        dp[now][tot-1][a[0]]=0;
        for(int i=0;i<n;i++)
        {
            swap(now,pre);
            memset(dp[now],0x3f,sizeof(dp[now]));
            for(int j=0;j<tot;j++)
                for(int k=0;k<tot;k++)
            {
                if (dp[pre][j][k]==inf) continue;
                dfs(j,k,a[i+1],0,now,dp[pre][j][k]);
            }
        }
        int ans=inf;
        for(int i=0;i<tot;i++)
            ans=min(ans,dp[now][i][0]);
        printf("%d\n",ans);
    }
    return 0;
}