HDU 1693 插头dp入门详解

放题目链接 https://vjudge.net/problem/22021/origin

给出一个n*m的01矩阵，1可走0不可通过，要求走过的路可以形成一个环且可以有多个环出现，问有多少不同的行走方案；

这道题目可以有多个环而不是限制为一个环，大大减弱了题目的难度，我还是想了好久。

先简单介绍一下轮廓线及插头,

这种dp进行状态转移时，每个方格对应着他自己的一条轮廓线，由上一个方格的轮廓线的状态，推导当前方格的轮廓线状态。

Normal
0

7.8 磅
0
2

false
false
false

EN-US
ZH-CN
X-NONE

/* Style Definitions */
table.MsoNormalTable
{mso-style-name:普通表格;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-priority:99;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.5pt;
mso-bidi-font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;
mso-font-kerning:1.0pt;}
table.MsoTableGrid
{mso-style-name:网格型;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-priority:39;
mso-style-unhide:no;
border:solid windowtext 1.0pt;
mso-border-alt:solid windowtext .5pt;
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-border-insideh:.5pt solid windowtext;
mso-border-insidev:.5pt solid windowtext;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.5pt;
mso-bidi-font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;
mso-font-kerning:1.0pt;}


		K1	K0
		K2 （3,3）
K4	K3

做的图不兼容只能这样看了，对于正在推倒的方格(3,3),蓝色那条轮廓线就是前一个方格(3,2)的轮廓线，根据这条蓝线的状态推导(3,3)的轮廓线状态，

由于每个格子都要通过，所以只要标记为'1'的格子对应的轮廓线上肯定要有插头，不然就不合法了，也就是说每个线只有两个情况0/1，

我们用一个整数的二进制表示这条线，假设x的二进制为k0k1k2k3k4,对应图中的蓝线旁的字符，进行状态压缩。

横线如果有插头，就是上下方向的，竖线就是左右方向的，能决定当前格子的就是k1和k2位了，其他位置不影响穿过当前格子的插头。

假设此格子是非障碍格，

当k1=k2=1时，表示有一个拐角状的插头穿过了这个格，显然这个格子不能再有插头了，将蓝线状态中的k1-->0,k2-->0,就是更新后的状态，让他加上蓝线状态的方案数

当k1=k2=0时，表示没有插头穿过格子，所以我们要给他加上一个拐角作为初始格，将k1->1,k2->1即可。

当k1=0,k2=1时，这个插头可以向右走或向下走，判断一下这两种情况是否合法，是的话进行转移。

当k1=1,k2=0时，同上。

如果这是个障碍格，只有k1=k2=0时才能转移，因为障碍格一定没插头。

还有一点要说的是由上一行最后一个状态向下一行第一个状态转移时，

由于上一行最后一个状态中k0位一定是0(边界定无右插头)，下一行第一个的k4也一定是0

所以直接右移一位即可。

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 int N,M,e[][];

 LL dp[][<<];

 LL solve()

 {

     memset(dp,,sizeof(dp));

     int cur=,i,j,k;

     dp[][]=;

     for(i=;i<=N;++i)

     {

         cur^=;

         memset(dp[cur],,sizeof(dp[cur]));

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

             dp[cur][k<<]=dp[cur^][k];

         for(j=;j<=M;++j)

         {

             cur^=;

             memset(dp[cur],,sizeof(dp[cur]));

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

             {

             if(!dp[cur^][k]) continue;

             int y=k&(<<(j-)),y1=<<(j-);

             int x=k&(<<j),x1=<<j;

             if(e[i][j]){

                if(x&&y) dp[cur][k^x1^y1]+=dp[cur^][k];

                if(!(x+y)) dp[cur][k|x1|y1]+=dp[cur^][k];

                if(x&&(!y)){

                 if(j<M&&e[i][j+]) dp[cur][k]+=dp[cur^][k];

                 if(i<N&&e[i+][j]) dp[cur][k^x1|y1]+=dp[cur^][k];

                }

                if(!x&&y){

                 if(j<M&&e[i][j+]) dp[cur][k^y1|x1]+=dp[cur^][k];

                 if(i<N&&e[i+][j]) dp[cur][k]+=dp[cur^][k];

                }

             }

             else{

               if(!(x+y)) dp[cur][k]+=dp[cur^][k];

             }

             }

         }

     }

     return dp[cur][];

 }

 int main()

 {

     int t,i,j;

     scanf("%d",&t);

     for(int cas=;cas<=t;++cas){

     memset(e,,sizeof(e));

         scanf("%d%d",&N,&M);

         for(i=;i<=N;++i)

             for(j=;j<=M;++j) scanf("%d",&e[i][j]);

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

     }

     return ;

 }

v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}


		K1	K0
		K2 （3,3）
K4	K3

Normal
0
false

7.8 磅
0
2

false
false
false

EN-US
ZH-CN
X-NONE

巴特西

HDU 1693 插头dp入门详解

最新文章

热门文章