HDU 1693 Eat the Trees 插头DP

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1693

意甲冠军：给定一个r*c的地，（r,c<=11），当中有的土地上种上了树，有些没有种上树。仅仅能在种上树的地上走，通过走若干个回路，来走遍全部种树的土地。问有多少种走法。

思路：不管怎样还是要先提供一个链接：http://wenku.baidu.com/view/4fe4ac659b6648d7c1c74633.html，是国家队论文。里面对于要提及的概念解说的十分清楚。

dp的过程是从左上角的点到右下角的点进行状态压缩dp。dp[i][j][k]表示第i行第j列时。轮廓线上从左到右是否存在插头的二进制状态k（0表示轮廓线上不存在插头，1表示轮廓线上存在插头）。

每行第零个状态是由右上角的状态第c个状态得到，详细过程是dp[i][0][j<<1]=dp[i-1][c][j]; 这是由于轮廓线从每行的第最后一种状态变成了每行的第一种状态（画画就明确了）。

状态转移也是依据插头的相应情况来写的，是由当前格子的下方轮廓线和右側轮廓线上是否存在插头来决定。

假设下方和右側都存在插头，那么左側和上方就都不能存在插头，所以状态时由上一个状态中相应两位都为0的情况得到。

假设下方和右側都不存在插头，那么左側和上方就都必定存在插头，所以状态时由上一个状态中相应两位都为1的情况得到。

假设下方存在插头，右側不存在插头。或者是右側存在插头，下方不存在插头，那么就可能存在上方存在插头或者是左側存在插头两种情况，分别寻找相应状态加上就可以。

P.S.果然原来插头DP的名字是基于连通性状态压缩的动态规划，本质还是状压…

代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 13
#define PI acos(-1.0)
#define seed 31//131,1313
//#define LOCAL
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
LL dp [maxn][maxn][1<<maxn] ;
int M [maxn][maxn] ;
int row,col;
LL solve(int r,int c)
{
    int tot=1<<(c+1);
    memset(dp,0,sizeof(dp));
    dp[0][c][0]=1;
    for(int i=1; i<=r; i++)
    {
        for(int j=0; j<tot; j++)
            dp[i][0][j<<1]=dp[i-1][c][j];
        for(int j=1; j<=c; j++)
        {
            int st1=(1<<j),st2=(1<<(j-1));
            for(int k=0; k<tot; k++)
            {
                if(M[i][j]==1)
                {
                    if((k&st1)==0&&(k&st2)==0)
                        dp[i][j][k]=dp[i][j-1][k+st1+st2];
                    else if((k&st1)!=0&&(k&st2)!=0)
                        dp[i][j][k]=dp[i][j-1][k-st1-st2];
//                    else
//                    {
//                        dp[i][j][k]+=dp[i][j-1][k];
//                        dp[i][j][k]+=dp[i][j-1][k^st1^st2];
//                    }//与下述状态转移等效。且更优美
                    else if((k&st1)==0&&(k&st2)!=0)
                    {
                        dp[i][j][k]+=dp[i][j-1][k-st2+st1];
                        dp[i][j][k]+=dp[i][j-1][k];
                    }
                    else
                    {
                        dp[i][j][k]+=dp[i][j-1][k-st1+st2];
                        dp[i][j][k]+=dp[i][j-1][k];
                    }
                }
                else if((k&st1)==0&&(k&st2)==0)
                    dp[i][j][k]=dp[i][j-1][k];
            }
        }
    }
    return dp[r][c][0];
}
int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    int T;
    scanf("%d",&T);
    for(int ii=1;ii<=T;ii++)
    {
        scanf("%d%d",&row,&col);
        for(int i=1; i<=row; i++)
            for(int j=1; j<=col; j++)
                scanf("%d",&M[i][j]);
        printf("Case %d: There are %I64d ways to eat the trees.\n",ii,solve(row,col));
    }
    return 0;
}