Eat the Trees（hdu 1693）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：在n*m的矩阵中，有些格子有树，没有树的格子不能到达，找一条或多条回路，吃完所有的树，求有多少中方法。

第一道真正意义上的插头DP，可参考陈丹琦的《基于连通性状态压缩的动态规划问题》，虽然我看了一遍，但只是了解了个大概，主要还是看别人的代码，自己画图理解。

插头和轮廓线的定义就不说了，在PPT中很好理解。

先说一下转移的方式，如下图（p和q是当前枚举到的格子所面临的需要更新插头的地方）：

通过在纸上画图，可以得出这么几个结论：

前一个状态的q和p都有插头的话，后一个状态的q和p都不能有插头。（因为一个显然格子只能有两个插头）

前一个状态的q和p都没有插头的话，后一个状态的q和p都必须有插头。（因为每个格子必须经过）

前一个状态的q和p任何一个有插头，后一个状态的q和p中只有一个有插头。

得到这几个结论之后，就可以方便地转移了。

最后在代码中有一点要注意的是，上一行的最后一列的状态可以转移到下一行第0列的状态，原因如下图：

代码参考于：http://www.cnblogs.com/zhuangli/archive/2008/09/04/1283753.html

#include<cstdio>

#include<iostream>

#include<cstring>

#define N 12

using namespace std;

int map[N][N],n,m;

long long dp[N][N][<<N];

int main(){

    int T,cas=;scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++)

                scanf("%d",&map[i][j]);

        memset(dp,,sizeof(dp));

        dp[][m][]=;

        for(int i=;i<=n;i++){

            for(int j=;j<(<<m);j++)

                dp[i][][j<<]=dp[i-][m][j];

            for(int j=;j<=m;j++){

                for(int k=;k<(<<m<<);k++){

                    int p=<<j;

                    int q=p>>;

                    bool x=k&p;

                    bool y=k&q;

                    if(map[i][j]){

                        dp[i][j][k]+=dp[i][j-][k^p^q];

                        if(x!=y)

                            dp[i][j][k]+=dp[i][j-][k];

                    }

                    else {

                        if(x==&&y==)

                            dp[i][j][k]=dp[i][j-][k];

                        else

                            dp[i][j][k]=;

                    }

                }

            }

        }

        printf("Case %d: There are %I64d ways to eat the trees.\n",++cas,dp[n][m][]);

    }

    return ;

}