精华内容
下载资源
问答
  • 插头dp

    2020-09-14 20:58:17
    之前在讲状压dp时还没有了解过插头dp,但状压的最后一道例题已经和插头dp很像了,这节就来解决一个插头dp的入门问题。 插头dp学习之前需要掌握或了解的东西:状压dp,哈希表,状压用来压缩一些局面,但可能出现的...

    插头dp

    之前在讲状压dp时还没有了解过插头dp,但状压的最后一道例题已经和插头dp很像了,这节就来解决一个插头dp的入门问题。
    插头dp学习之前需要掌握或了解的东西:状压dp,哈希表,状压用来压缩一些局面,但可能出现的情况很多导致状压后的数很大,这时候就可以使用哈希表来仅存放已出现的局面,避免开辟太大的数组。
    插头dp有几个关键词,当关键词出现时可以向这方面考虑:超小数据范围,网格图,连通性。
    还需要理解一些抽象的定义:
    插头
    一个格子以某种方式向另一个格子相连,相连的位置叫插头,具体的类似拼图的凹槽与凸出这就是一种插头。
    轮廓线
    我们选取一个格子(i,j)作为决策点时,图中黄线就是轮廓线
    在这里插入图片描述
    轮廓线可以记录影响当前决策格或以后决策格做决策的要素(插头状态)。

    例题:URAL1519

    题目大意:一个网格图中有若干障碍格子,求其他格子的哈密尔顿回路总数

    题解
    这道题的数据范围很小可以使用状态压缩,又要求连通性那就使用插头dp。
    首先定义轮廓线设轮廓线的单位部分从左到右有a,b,c,d四个插头,我们发现如果a,c连通,那么b,d就不可能连通,这其实是一个括号匹配问题,于是我们可以进一步定义,如果a,b连通左边的a记为1,右边的b记为2。
    这样每个轮廓线的单位部分就有了三种情况,三进制数不好运算我们可以使用四进制数记录。
    16位的四进制数太大了我们需要一个方法减少一些空间使用,这就用到了哈希表通过哈希表我们可以只记录出现了的状态,其中大量的无意义的状态就不用储存了。
    综上我们确定了我们的用于状态转移的状态f(i,j,S)f(i,j,S)其中S为轮廓线状态。

    状态转移方程

    mp数组是网格的状态,0为有障碍,1为无障碍。
    每次转移我们需要将决策格的上,左边转移为下,右边。其中决策格的上,左边会影响到我们当前决策格的决策,为了方便我们将其记为b1,b2,设轮廓线为a0a1a2a3a4
    在这里插入图片描述
    1.当前决策格有障碍
    那么只有这个格子没有连通的时候才是合法情况,转移后轮廓线状态不变。

    if(mp[i][j]){if(!b1&&!b2) ins(zt,num);}
    

    其中ins()函数是向轮廓线状态zt的方案加上num(就是简化的 dp[now][zt]+=dp[las][zt]dp[now][zt]+=dp[las][zt`])。
    2.当前决策无障碍:
    (1)b1,b2都为0
    那么只有决策格只有一种情况如图
    在这里插入图片描述
    转移后ai-1=1,ai=2。

    else if (!b1 && !b2)
    	{if (mp[i + 1][j] && mp[i][j + 1]) ins(zt + bin[j - 1] + 2 * bin[j], num);}
    

    这里即使不判断要连通的格子是不是有障碍,也可以正确给出答案,但是会额外在哈希表中创立许多无效方案,加大了时间复杂度与空间复杂度,所以这里选择在转移前多判断一下。
    (2)b1与b2其中一个为0
    b2=0时有两张情况,第一种交换ai-1与ai
    在这里插入图片描述
    第二种轮廓线不变
    在这里插入图片描述

    if(b1&&!b2){
    	if(mp[i][j+1]){ins(zt-bit[j-1]*b1+bit[j]*b1,num);}
    	if(mp[i+1][j]){ins(zt,num);}
    }
    

    b1=0时同理。

    if(!b1&&b2){
    	if(mp[i][j+1]){ins(zt-bit[j]*b2+bit[j-1]*b2,num);}
    	if(mp[i+1][j]){ins(zt,num);}
    }
    

    (3)b1=b2
    当b1=b2=1时,当b1与b2是不同的连线可以连线,但是b1与b2可能已经连上了,所以我们需要沿着轮廓线去寻找这条线是否已经连上了。(不是单纯沿轮廓线寻找一个为2的插头,因为中间可能还有更多没连上的线)
    在这里插入图片描述
    转移后ai-1,ai=0,要注意的是连线后要把左边的一个2插头改为1插头。

    if(b1==1&&b2==1){
    	int k=1;
    	for(int t=j+1;t<=m;t++){
    		if((zt>>(2*t)%4)==1)k++;
    		if((zt>>(2*t)%4)==2)k--;
    		if(!k){ins(zt-bit[j]-bit[j-1]-bit[t],num);break;}
    	}
    }
    

    b1=b2=2时,同理。

    if(b1==2&&b2==2){
    	int k=1;
    	for(int t=j-2;t>=0;t--){
    		if((zt>>(2*t)%4==2)k++;
    		if((zt>>(2*t)%4==1)k--;
    		if(!k){ins(zt+bit[t]-bit[j]*2-bit[j-1]*2,num);break;}
    	}
    }
    

    (4)b1=2,b2=1
    在这里插入图片描述
    这个转移比较容易

    if(b1==2&&b2==1) ins(zt-bit[j]-bit[j-1]*2,num);
    

    (5)b1=1,b2=2
    在这里插入图片描述
    这种情况一定要注意如果连线就提前形成一个回路,只有最后一个非障碍的格子才可以连起来,形成回路。

    完整代码

    #include<iostream>
    using namespace std;
    const int MAX = 3e5 + 5, Has = 3e5 - 11;
    int n, m, e1, e2, las, now = 0;
    long long ans;
    int mp[15][15], bin[15], tot[2];
    int h[MAX];
    
    struct Hashtable//哈希表,a用来存轮廓线状态,js用来存方案数,next存放哈希冲突时下一个格子的坐标
    {
    	long long js[2];
    	int a[2], next;
    }has[MAX];
    
    void ins(int zt, int num)
    {
    	int tmp = zt % Has + 1;
    	for (int i = h[tmp]; i; i = has[i].next)
    		if (has[i].a[now] = zt) { has[i].js[now] += num; return; }
    	has[++tot[now]].next = h[tmp];
    	h[tmp] = tot[now];
    	has[tot[now]].js[now] = num;
    	has[tot[now]].a[now] = zt;
    }
    
    void work()
    {
    	tot[now] = 1; has[1].a[now] = 0; has[1].js[now] = 1;
    	for (int i = 1; i <= n; i++)
    	{
    		for (int j = 1; j <= tot[now]; j++)has[j].a[now] <<= 2;//换行转移
    		for (int j = 1; j <= m; j++)
    		{
    			las = now; now ^= 1;
    			memset(h, 0, sizeof(h));
    			tot[now] = 0;
    			for (int k = 1; k <= tot[las]; k++)
    			{
    				int zt = has[k].a[las];
    				long long num = has[k].js[las];
    				int b1 = (zt >> (2 * (j - 1))) % 4, b2 = (zt >> (2 * j)) % 4;//提取决策格上的轮廓线
    				if (!mp[i][j]) { if (!b1 && !b2)ins(zt, num); }
    				else if (!b1 && !b2)
    				{
    					if (mp[i + 1][j] && mp[i][j + 1]) ins(zt + bin[j - 1] + 2 * bin[j], num);
    				}
    				else if (!b1&&b2) {
    					if (mp[i][j + 1]) ins(zt, num);
    					if (mp[i + 1][j]) ins(zt - bin[j] * b2 + bin[j - 1] * b2, num);
    				}
    				else if (b1 && !b2) {
    					if (mp[i][j + 1]) ins(zt - bin[j - 1] * b1 + bin[j] * b1, num);
    					if (mp[i + 1][j]) ins(zt, num);
    				}
    				else if (b1 == 1 && b2 == 1) {
    					int kl = 1;
    					for (int t = j + 1; t <= m; ++t) {
    						if ((zt >> (t * 2)) % 4 == 1) ++kl;
    						if ((zt >> (t * 2)) % 4 == 2) --kl;
    						if (!kl) { ins(zt - bin[j] - bin[j - 1] - bin[t], num); break; }
    					}
    				}
    				else if (b1 == 2 && b2 == 2) {
    					int kl = 1;
    					for (int t = j - 2; t >= 0; --t) {
    						if ((zt >> (t * 2)) % 4 == 1) --kl;
    						if ((zt >> (t * 2)) % 4 == 2) ++kl;
    						if (!kl) { ins(zt + bin[t] - 2 * bin[j] - 2 * bin[j - 1], num); break; }
    					}
    				}
    				else if (b1 == 2 && b2 == 1) ins(zt - 2 * bin[j - 1] - bin[j], num);
    				else if (i == e1 && j == e2) ans += num;
    			}
    		}
    	}
    }
    
    int main()
    {
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++)
    	{
    		for (int j = 1; j <= m; j++)
    		{
    			char ch;
    			ch = getchar();
    			while (ch != '*'&&ch != '.')ch = getchar();
    			if (ch == '.')
    			{
    				mp[i][j] = 1;
    				e1 = i;
    				e2 = j;
    			}
    		}
    	}
    	bin[0] = 1;
    	for (int i = 1; i <= 12; i++)bin[i] = bin[i - 1] << 2;
    	work();
    	cout << ans << endl;
    	system("pause");
    	return 0;
    }
    

    本题除了转移方程的策略选择,还有哈希表的构造,本题哈希需要存储轮廓线状态,方案数两种数据各两次,这里使用了一个结构体包装,如果拆成单个数组也可以通过相同的索引调用数据。
    本题的哈希表处理哈希冲突的方式是链表法,将冲突的元素通过next连接到了链表头。
    这里的代码我发现与储存图的链式向前星相似(都是用数组写链表)可以结合理解。
    还有本题用到了滚动数组减少空间,之前状压dp也讲到了。

    展开全文
  • 插头DP

    2019-09-27 15:43:07
    插头DP主要用来处理一系列基于连通性状态压缩的动态规划问题,处理的具体问题有很多种,并且一般数据规模较小。 由于棋盘有很特殊的结构,使得它可以与“连通性”有很强的联系,因此插头DP最常见的应用要数在棋盘...

    先%%学长优秀博客:%%

    并借用他的定义:

    插头DP主要用来处理一系列基于连通性状态压缩的动态规划问题,处理的具体问题有很多种,并且一般数据规模较小。

    由于棋盘有很特殊的结构,使得它可以与“连通性”有很强的联系,因此插头DP最常见的应用要数在棋盘模型上的应用了。

    直接上题

    一、HDU1693 Eat the Trees

    题目大意:给出一张n*m有障碍的棋盘,要求用任意条回路遍历整个棋盘,不能经过障碍格子,要求统计不同的行走方案数。

     

    Sample Input

     

    2
    6 3
    1 1 1
    1 0 1
    1 1 1
    1 1 1
    1 0 1
    1 1 1
    2 4
    1 1 1 1
    1 1 1 1

     

    Sample Output

     

    Case 1: There are 3 ways to eat the trees.

     

    Case 2: There are 2 ways to eat the trees.

     

     

     

    具体过程请参考学长博客,我就不搬了(没素质),上解释代码

    重点看Execution函数的分情况讨论的实现 (Execution中判断x==n,y==m的状况可以不写正常转移)

     1 ^:不同则1,相同则0
     2 &:全1则1,有0则0
     3 #include <cstdio>
     4 #include<iostream>
     5 #include <cstring>
     6 using namespace std;
     7 typedef long long LL;
     8 int n,m,bin[20],mp[13][13];
     9 LL f[13][13][(1<<12)+10];//f[i][j][k]表示转移完第i行第j列插头状态为k时的方案数
    10 inline void Execution(int x,int y)
    11 {
    12     int plug1=bin[y-1],plug2=bin[y];//分类bin[y-1]为左插头,bin[y]为上插头
    13     if(x==n&&y==m)//最后状态只走0即可
    14     {
    15         if(mp[x][y])//!障碍且j状态没有插头,^后为有两个插头,及由y-1有两个插头转移
    16             f[x][y][0]+=f[x][y-1][plug1^plug2];
    17         else//障碍并且转移后保证没有插头及一定合法
    18             f[x][y][0]=f[x][y-1][0];//所以没有插头连向它才合法转移
    19         return;
    20     }
    21     for(int j=0;j<bin[m+1];j++)//枚举状态(此时第m+1个插头可以为1)
    22         if(mp[x][y])//!障碍
    23         {
    24             f[x][y][j]+=f[x][y-1][j^plug1^plug2];
    25             //plug1^plug2的第y-1,y这两位为1(从0开始)
    26             //如果j状态有两个插头,^后为没有插头,及由y-1的没有插头转移
    27             //如果j状态没有插头,^后为有两个插头,及由y-1有两个插头转移
    28             //如果j状态有一个,^10变01,及由y-1有一个插头且不转向转移来
    29             //10变10没法实现,只能排除00/11的情况,直接变
    30             if(((j>>(y-1))&1)==((j>>(y))&1)) continue;//都为没插头或都有
    31             f[x][y][j]+=f[x][y-1][j];//10变10,及由y-1有一个插头转向转移
    32         }
    33         else//障碍
    34         {
    35             if(!(j&plug1)&&!(j&plug2))//y-1处理完后该格没有左插头和上插头,同((!((j>>(y-1))&1))&&(!((j>>y)&1)))
    36                 f[x][y][j]=f[x][y-1][j];//及没有插头连向它才合法转移
    37             else f[x][y][j]=0;//否则方案数为0
    38         }
    39 }
    40 int main()
    41 {
    42     int t;
    43     scanf("%d",&t);
    44     bin[0]=1;
    45     for(int i=1;i<=15;i++) //2^最大方案数
    46         bin[i]=bin[i-1]<<1;
    47     //cout<<bin[8]<<endl;
    48     for(int u=1;u<=t;u++)
    49     {
    50         scanf("%d%d",&n,&m);
    51         for(int i=1;i<=n;i++)
    52             for(int j=1;j<=m;j++)
    53                 scanf("%d",&mp[i][j]);
    54         memset(f,0,sizeof(f));
    55         f[1][0][0]=1;//*************初始化第0格*****************//
    56         for(int i=1;i<=n;i++)
    57         {
    58             for(int j=1;j<=m;j++) Execution(i,j);//逐格递推
    59             if(i!=n)//行间转移:当前行的0到m-1转移到下一行的1到m
    60                 for(int j=0;j<bin[m];j++)//bin[m]及第m个插头不可能为1
    61                     f[i+1][0][j<<1]=f[i][m][j];//初始化第0格
    62         }
    63         printf("Case %d: There are %lld ways to eat the trees.\n",u,f[n][m][0]);//最后状态不能再有插头
    64     }
    65 }

     注意点:(自己的zz错误)

    (1)行间转移没判 i!=n        59行

    (2)插头从0到m,第m个插头不能为1,写成bin[m+1]         60行

    (3)行间转移j<<1写成j>>1,左移1后i+1行的第0位为0         61行

    (4)判断都有或没有插头跳过时没&1            30行

    转载于:https://www.cnblogs.com/qwertyuiopasdfghjklzxcvbnm/p/11260734.html

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,303
精华内容 521
关键字:

插头dp