hdu 1693 : Eat the Trees 【插头dp 入门】

题意：给出一个n*m大小的01矩阵，在其中画线连成封闭图形，其中对每一个值为1的方格，线要恰好穿入穿出共两次，对每一个值为0的方格，所画线不能经过。

参考资料：《基于连通性状态压缩的动态规划问题》　　——陈丹琦 2008年国家集训队论文

递推过程中，按照遍历行->遍历行上每一格->遍历 “轮廓线跨过该格时所有可能的状态变化” 的顺序

这样复杂度是 O(n*m*2^m⁺¹) （m+1是因为轮廓线上有m个单元是与列数对应的，另有一单独的竖线单元）

问题关键点在于解决 “轮廓线跨过该格时所有可能的状态变化”

首先是由第i行到第i+1行的递推关系。显然，第i+1行上，轮廓线未跨过任何方格，与在第i行，轮廓线跨过了所有方格，这两者轮廓线的形态是相同的，不过，前者的状态state1应表示为后者的状态state2<<1，在代码中，计数关系通过 for(int k=0;k<M;k++) dp[i][0][k<<1]=dp[i-1][m][k]; 来实现。

然后是在同一行上跨过某一格时的递推关系。不考虑方格值为0，这道题里面共有四种情况，对于具体某一格而言，即 00->11,01->10,10->01,11->00。对于方格值为0的情况，显然只能是00->00。

后继状态总计数=sigma合法的前驱状态。

具体可以借助代码来理解

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn=;

int n,m;

int mp[maxn][maxn];

LL dp[maxn][maxn][<<maxn];

LL solve()

{

    int M=<<(m+);        //轮廓线上状态总数

    dp[][m][]=;

    for(int i=;i<=n;i++)    //遍历行

    {

        for(int k=;k<M;k++)

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

        for(int j=;j<=m;j++)    //j用来指示轮廓线中小竖线的位置

        {

            int state1=(<<j),state2=(<<(j-));

            for(int k=;k<M;k++)

            {

                if(mp[i][j])

                {

                    if((k&state1)==&&(k&state2)==)

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

                    else if((k&state1)!=&&(k&state2)!=)

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

                    else if((k&state1)==&&(k&state2)!=)

                    {

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

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

                    }

                    else

                    {

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

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

                    }

                }

                else

                    if((k&state1)==&&(k&state2)==)

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

            }

        }

    }

    return dp[n][m][];

}

int main()

{

    int T,kase=;

    scanf("%d",&T);

    while(T--)

    {

        memset(dp,,sizeof(dp));

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

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

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

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

        printf("Case %d: There are %lld ways to eat the trees.\n",++kase,solve());

    }

}

巴特西

hdu 1693 : Eat the Trees 【插头dp 入门】

最新文章

热门文章