Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

好学易懂 从零开始的插头DP(一)

idyllic 2020-11-22 23:33:00 阅读数:7 评论数:0 点赞数:0 收藏数:0

好学易懂 从零开始的插头DP(一)

写在前面

这是一篇,以蒟蒻视角展开的梳理总结。更改了一些顺序,变化了一些细节。方便蒟蒻学习理解(起码本蒟蒻是这样)。大佬们可以直接看其它大佬的博客,可以学的更快。

你必须要学会的前置知识:状态压缩DP
学不会依旧可以读,但是推荐学的前置知识:哈希

论文贡前面,建议读完博客再看。
《基于连通性状态压缩的动态规划问题》

什么是插头DP

很显然,是一个关于插头的动态规划。那么,什么是插头呢?

如图我们在一个方格内,关于格点画一条闭合回路。

对于每一个方格,内部,有六种情况
在这里插入图片描述
不难发现,对于回路里的任何一个方格,四条边中,有且仅有两个与表示路径的蓝色线相交。这也很好理解,进一次,出一次,C(4,2)=6。
我们现在把格子里的蓝色线条,变成从格子中心指向外边的→。

这个箭头,也就是所谓的插头。

例题

我们结合一个例题来看,这个题目是洛谷模板题的弱化版,很多博客放在了模板题后的第一题,结合个人经历我觉得它比模板题更适合作第一题。
题目链接:HDU1693 or 洛谷P5074
题目大意:给一个n*m的方格,有些格子必须走,有些格子不能走。问有多少种不同的闭合回路。(1<=n,m<=12)

那么,把回路模型变成插头模型有什么好处或者性质呢?
1:首先,我们可以发现,如果一个格子上方的格子有下插头,那这个格子一定有上插头。其它方向类似。
2:一个格子的合理取法合且仅合相邻的格子有关。

观察下第二点,它其实代表了无后效性。假设我们从上到下,从左到右的处理每一个格子,那么我们只需要记录部分格子的状态即可,再往上的格子具体状态不用知道。
在这里插入图片描述

如上图,对于当前格子,我们只需要知道红色的这些格子就行了,再上面的格子具体的取法,已经不会对下面任何未处理的格子产生影响。

已经掌握了状态压缩的你,一定能轻松的算出状态总数,每个格子6种,维护n个格子。总共6 n 6^n6n种状态,好的,完蛋,只有2e9个状态。
在这里插入图片描述
别急,我们真的需要2e9个状态嘛?这些格子里,指向彼此和已经处理过的格子的插头,显然是废物信息。我们实际上只需要知道这些插头嘛:
在这里插入图片描述
蓝色的是其它格子需要用到的,黄色的是当前格子需要用到的。我们只需要知道这m+1个箭头是否存在就可以了。总共2 m ∗ 2 2^m*22m2个状态。再乘上n和m,时空复杂度都绰绰有余。
那么,怎么实现呢?我们要解决两个问题。

1:已知这些插头的情况下,这个方格该如何填。
2:填完这个方格后,如何得到下一个方格所需要的插头状态,更特殊的,如何从上一行行末,变到下一行行初。

这两个问题,其实都不是很难,稍微思考下,都可以独立解答,建议思考后再往下看。图片挡下文大法。
在这里插入图片描述
问题1:
1:如果当前格子存在左侧插头和上方插头,那么只有一种合理填法。
在这里插入图片描述
2:如果仅存在左侧插头,那么有两种合理填法。

在这里插入图片描述
3:如果仅存在上方插头,那和上一种类似,也是两种填法。
在这里插入图片描述
在这里插入图片描述
4:如果都不存在呢?只有一种填法
在这里插入图片描述
问题2:
解答了问题1,显然我们也得到了问题2的解答,毕竟我们填出了这个格子,自然知道插头分布。唯一特殊的是上一行末到这一行头的处理。上一行末不可能有右插头,那我们直接把上一行末状态的表示最后是否存在右插头的位置去掉,再添加一个表示没有左插头的位,不就表示出了这一行第一个的状态了嘛,为了方便写,下方的代码里,我用dp[i][0][mask]表示转移后的上一行行末状态。
在这里插入图片描述
到这里,我们已经得到了解法了,成熟的评测机,应该自动AC了吧(划去)。插头DP还是要多写的,千万自己写一遍,别忘了,这只是模板题的弱化。
这里提供一份代码(洛谷AC)

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 using namespace std;
 5 int n,m,maxk,a[13][13];
 6 long long dp[13][13][1<<14];
 7 void init()
 8 {
 9 scanf("%d%d",&n,&m);
10 maxk=(1<<(m+1))-1;
11 for (int i=1;i<=n;i++)
12  {
13 for (int j=1;j<=m;j++)
14  {
15 scanf("%d",&a[i][j]);
16  }
17  }
18 memset(dp,0,sizeof(dp));
19 }
20 void solve()
21 {
22 int prei,prej;
23 dp[0][m][0]=1;
24 for (int i=1;i<=n;i++)
25  {
26 for (int k=0;k<=maxk;k++)
27  {
28 dp[i][0][k<<1]=dp[i-1][m][k];
29  }
30 for (int j=1;j<=m;j++)
31  {
32 prei=i;
33 prej=j-1;
34 for (int k=0;k<=maxk;k++)
35  {
36 int b1=(k>>(j-1))&1;
37 int b2=(k>>j)&1;
38 if (!a[i][j])
39  {
40 if (!b1&&!b2) dp[i][j][k]+=dp[prei][prej][k];
41  }
42 else if (!b1&&!b2)
43  {
44 dp[i][j][k+(1<<j)+(1<<(j-1))]+=dp[prei][prej][k];
45  }
46 else if (b1&&!b2)
47  {
48 dp[i][j][k]+=dp[prei][prej][k];
49 dp[i][j][k+(1<<(j-1))]+=dp[prei][prej][k];
50  }
51 else if (!b1&&b2)
52  {
53 dp[i][j][k]+=dp[prei][prej][k];
54 dp[i][j][k-(1<<(j-1))]+=dp[prei][prej][k];
55  }
56 else if (b1&&b2)
57  {
58 dp[i][j][k-(1<<j)-(1<<(j-1))]+=dp[prei][prej][k];
59  }
60  }
61  }
62  }
63 printf("%lld\n",dp[n][m][0]);
64 }
65 int main()
66 {
67 int t;
68 scanf("%d",&t);
69 while (t--)
70  {
71  init();
72  solve();
73  }
74 return 0;
75 }
View Code of P5074

电脑前这个努力的帅气身影是谁呢?そう 私 です

版权声明
本文为[idyllic]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/idyllic/p/14022305.html