插头DP讲解+[BZOJ1814]:Ural 1519 Formula 1(插头DP)

2024-01-17 03:50

本文主要是介绍插头DP讲解+[BZOJ1814]:Ural 1519 Formula 1(插头DP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.什么是插头$DP$?

插头$DP$是$CDQ$大佬在$2008$年的论文中提出的,是基于状压$D$P的一种更高级的$DP$多用于处理联通问题路径问题,简单回路问题,多回路问题,广义回路问题,生成树问题)。

插头$DP$每道题都不一样,且需要进行较为繁琐的分类讨论,所以插头$DP$十分锻炼思维的严谨性和全面性。


2.插头$DP$思路

 $\mathcal{A.}$状态确立

  $\alpha.$插头

   插头表示一种联通状态

   在棋盘模型中,一个格子有向某方向的插头,表示这个格子在这个方向与插头那边的格子相连。

   注意:插头并不是说将要去某处的虚拟状态,而是已经到达某处的现实状态

   我们需要考虑的是接下来往哪里走,因为如果有一个插头指向当前格子,说明当前格子已经与插头的来源有联通了。

   有了插头,就方便多啦,我们一般需要的是进行逐格递推,通俗的讲,就是跑一遍。

  $\beta.$轮廓线

   轮廓线就是一条分界线,至于它为什么叫轮廓线,我也不知道,就像$CDQ$为什么叫$CDQ$一样,她也不知道,但是她爸妈知道。

   你可以感性的将它理解为是“已经决策了的格子”与“还没有决策的格子”的分界线。

   但是,轮廓线的用途不止如此。

   轮廓线还兼容了存储这条分界线上插头状态的作用。

   需要注意的是,假设一行内有$m$个格子,那么会有$m+1$个插头,为什么呢?

   看一下下面的这张图:

   

   显然一行内有$4$个格子,但是有$5$个插头,多出来的那一个插头在当前正在决策的那个格子的右侧。

   个人习惯将插头编号为$1~m$。

   一般数据范围比较小,我们可以用状压来存储,即定义$dp[i][j][state]$表示当前决策到$(i,j)$这个点,状态为$state$的方案数(或代价,$etc$)。

  $\gamma.$插头与轮廓线的结合

   插头与轮廓线结合在一起,就会碰撞出一些美丽的火花。

   我们递归的时候就是依据插头的存在性,来求出所有能转移到的合法状态。

   在回路问题中,对于一个状态一个格子恰好有两个插头,一个“进来”,一个“出去”。

 $\mathcal{B}.$记录状态

  下面来介绍三种记录状态的方式:

  $\alpha.$最小表示法

   为了方便,所有有障碍的格子记为$0$,第一个非障碍的格子以及所有与它相连的格子标记为$1$,第一个未标记的格子以及与它相邻的格子标记为$2$……

   重复以上的过程,直到所有的格子都标记完毕。

   举个栗子:

    $1,2,5$联通,$3,6$联通,$4$自己和自己卡在一起,那么其最小表示法即为${1,1,2,3,1,2}$。

  $\beta.$括号表示法

   先来看一个性质:假设一条轮廓线上有$4$个插头$a,b,c,d$,$a$与$c$联通且不与$b$联通,那么$b$与$d$肯定也不联通。

   这个性质很重要,因为它适用于所有的棋盘问题

   

   就像这样,显然如果$b$与$d$也相交的话就不可能满足情况了。

   再具体一点:

   

   相信细心的你一定会发现,轮廓先上方的路径都是由若干条互不相交的路径构成的,原因就是再上面那张图。

   每条路径上的两个端点也会恰好对应轮廓线上的两个插头

   再来明确一点,对于不同的插头,我们称它们为左插头或右插头,并不是指它们的方向,而是指在途中相对的左右,如下图:

   

   有点跑题了,这种“不交叉”很容易让我们联想到括号匹配,左括号为进栈,右括号为出栈,左括号一定与右括号一一对应。

   当然有可能会让你想到卡特兰数,这点很重要,能帮你卡常。

  $\gamma.$状态的编码

   利用状压的思想,我们将每行$m+1$个状态用一个$m+1$位的$k$进制数表示,在做题的时候建议将$k$改为$2$的$n$次幂,方便进行为运算,运行速度会有很大的提升(前提空间允许)。

   小技巧:如需大范围修改联通状态,可以选择$\Theta(m)$将其解码到一个数组里,修改后在$\Theta(n)$将其计算为$k$进制数,而对于只需要进行局部修改的情况可以直接用$(x\ div\ p^{i-1})mod\ p$来获取第i位的状态,使用$+x\times p^{i-1}$来对第i位的状态进行修改。

 $\mathcal{C}.$状态转移

  $\alpha.$行间转移

   显然,第$i$行第$j$列的下插头决定了第$i+1$行第$j$列有没有上插头,因此需要将这个信息传递给下一行。

   当枚举到一行的最后一个格子的时候,第$m$个插头一定为$0$(即为没有),如下图。

   

   细心的你还能发现,在行间转移之前的第$0~m-1$个插头会变成行间转移之后的第$1~m$个插头,如下图。

   

   所以,我们每次只需要将上一行的状态左移一位即可。

   代码$\downarrow$:

for(int j=1;j<=cnts[cnt];j++)state[cnt][j]<<=1;

   打法奇特,请多谅解。

  $\beta.$逐格转移

   因题而异,比行间转移复杂,一般分为多种情况,需要分类讨论。

   在很多的状态转移中都出现了以下三种情况:

    $\mathfrak{a}.$新建一个联通分量:

     这个情况只出现在转移位置的轮廓线上没有下插头和右插头:

     

     在上图中,这个格子没有上插头,也没有左插头,那么由于我们要遍历整张图,所以我们要新建插头,把这个格子与其他格子连起来,相应的,我们要把原来轮廓线对应位置的插头改为$1$。

    $\mathfrak{b}.$合并两个联通分量:

     不连通的话,当然这样做会把他们变联通:

     

     这个位置有上插头,也有左插头。由于我们不要求只有一条回路,因此回路可以在这里结束。我们直接更新答案即可。

    $\mathfrak{c}.$保持原有的联通分量:

     

     只有一个插头。那么这个插头可以向其他方向走:向下和向右均可以。所以我们修改一下轮廓线并更新对应状态的答案即可。

 $\mathcal{D}.$优化

  可以使用$hash$表进行优化,下面附一个此题中我用的$hash$表的代码$\downarrow$:

int pre_hash[600000],at;
int sta_hash[2][600000],cnts[2];
void hash_map(int sta,long long val)
{int key=sta%590027;for(int i=pre_hash[key];i;i=hash[i].nxt)if(sta_hash[cnt][hash[i].to]==sta)//如果这个状态已经存在,就加上{dp[cnt][hash[i].to]+=val;return;}sta_hash[cnt][++cnts[cnt]]=sta;//不存在这个状态就新建dp[cnt][cnts[cnt]]=val;hash[++at].nxt=pre_hash[key];hash[at].to=cnts[cnt];pre_hash[key]=at;
}

例题$\downarrow$


题目描述

一个$m\times n$的棋盘,有的格子存在障碍,求经过所有非障碍格子的哈密顿回路个数。


输入格式

第$1$行,$n,m$。
从第$2$行到第$n+1$行,每行一段字符串($m$个字符),"*"表不能铺线,"."表必须铺。


输出格式

输出一个整数,表示总方案数。


样例

样例输入$1$:

4 4
**..
....
....
....

样例输出$1$:

2

样例输入$2$:

4 4
....
....
....
....

样例输出$2$:

6


数据范围与提示

$2\leqslant n,m\leqslant 12$。


题解

典型的插头$DP$板子题,洛谷更是将它作为了【模板】插头$dp$。

这道题中,我们需要用$3$进制来表示状态,$0$表示无插头,$1$表示左插头,$2$表示右插头,我使用的是$4$进制,弃掉一位,但是方便位运算的操作。

下面来列举一下这道题的$7$种情况:

 $\alpha.$有障碍:

if(!Map[i][j]){if(!down&&!right)hash_map(sta,ans);}

 $\beta.$

if(!down&&!right){if(Map[i+1][j]&&Map[i][j+1])hash_map(sta+2*(1<<bit[j])+(1<<bit[j-1]),ans);}

 $\gamma.$

if(down&&!rght)
{if(Map[i][j+1])hash_map(sta,ans);if(Map[i+1][j])hash_map(sta+down*((1<<bit[j-1])-(1<<bit[j])),ans);
}

 $\delta.$

if(!down&&right)
{if(Map[i+1][j])hash_map(sta,ans);if(Map[i][j+1])hash_map(sta+right*((1<<bit[j])-(1<<bit[j-1])),ans);
}

 $\epsilon.$

if(down==1&&rght==1)
{int count=1;for(int l=j+1;l<=m;l++){if((sta>>bit[l])%4==1)count++;if((sta>>bit[l])%4==2)count--;if(!count){hash_map(sta-(1<<bit[j])-(1<<bit[j-1])-(1<<bit[l]),ans);break;}}
}

 注意此时我们不仅需要将两个左插头减去,而且还要将左边的右插头变成左插头。

 $\zeta.$

if(down==2&&rght==2)
{int count=1;for(int l=j-2;l>=0;l--){if((sta>>bit[l])%4==1)count--;if((sta>>bit[l])%4==2)count++;if(!count){hash_map(sta-2*(1<<bit[j])-2*(1<<bit[j-1])+(1<<bit[l]),ans);break;}}
}

 注意上面依然需要减去两个右插头,再把右边的左插头变成右插头。

 $\eta.$

if(down==1&&rght==2){hash_map(sta-(1<<bit[j])-2*(1<<bit[j-1]),ans);}

 此时我们合并了一个右插头和一个左插头,减去就好了。

 $\theta.$形成了一个回路,只有在最后一个格子才有可能形成回路。

if(down==2&&rght==1&&i==endx&&j==endy)ansss+=ans;

$7$种情况已经列举完了,代码实现细节不少,要注意。


代码时刻

#include<bits/stdc++.h>
using namespace std;
struct hash_table
{int nxt;int to;
}hash[600000];
char ch[20];
int pre_hash[600000],at;
int sta_hash[2][600000],cnts[2];
bool Map[15][15];
int bit[15];
bool cnt;
int endx,endy;
long long ans,ansss,dp[2][600000];
void hash_map(int sta,long long val)//hash表
{int key=sta%590027;for(int i=pre_hash[key];i;i=hash[i].nxt)if(sta_hash[cnt][hash[i].to]==sta){dp[cnt][hash[i].to]+=val;return;}sta_hash[cnt][++cnts[cnt]]=sta;dp[cnt][cnts[cnt]]=val;hash[++at].nxt=pre_hash[key];hash[at].to=cnts[cnt];pre_hash[key]=at;
}
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",ch+1);for(int j=1;j<=m;j++)if(ch[j]=='.'){Map[i][j]=1;endx=i;endy=j;}}for(int i=1;i<=m;i++)//预处理一下,方便下面处理bit[i]=(i<<1);cnts[0]=1;dp[0][1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=cnts[cnt];j++)sta_hash[cnt][j]<<=2;//将状态左移一位for(int j=1;j<=m;j++){at=0;memset(pre_hash,0,sizeof(pre_hash));cnt^=1;cnts[cnt]=0;for(int k=1;k<=cnts[cnt^1];k++){int sta=sta_hash[cnt^1][k];//提取状态long long ans=dp[cnt^1][k];int down=(sta>>bit[j])%4;//提取插头信息,下同int rght=(sta>>bit[j-1])%4;if(!Map[i][j])//α{if(!down&&!rght)hash_map(sta,ans);}else if(!down&&!rght)//β{if(Map[i+1][j]&&Map[i][j+1])hash_map(sta+2*(1<<bit[j])+(1<<bit[j-1]),ans);}else if(down&&!rght)//γ{if(Map[i][j+1])hash_map(sta,ans);if(Map[i+1][j])hash_map(sta+down*((1<<bit[j-1])-(1<<bit[j])),ans);}else if(!down&&rght)//δ{if(Map[i+1][j])hash_map(sta,ans);if(Map[i][j+1])hash_map(sta+rght*((1<<bit[j])-(1<<bit[j-1])),ans);}else if(down==1&&rght==1)//ε{int count=1;for(int l=j+1;l<=m;l++){if((sta>>bit[l])%4==1)count++;if((sta>>bit[l])%4==2)count--;if(!count){hash_map(sta-(1<<bit[j])-(1<<bit[j-1])-(1<<bit[l]),ans);break;}}}else if(down==2&&rght==2)//ζ{int count=1;for(int l=j-2;l>=0;l--){if((sta>>bit[l])%4==1)count--;if((sta>>bit[l])%4==2)count++;if(!count){hash_map(sta-2*(1<<bit[j])-2*(1<<bit[j-1])+(1<<bit[l]),ans);break;}}}else if(down==1&&rght==2)//η{hash_map(sta-(1<<bit[j])-2*(1<<bit[j-1]),ans);}else if(down==2&&rght==1&&i==endx&&j==endy)ansss+=ans;//θ}}}printf("%lld",ansss);return 0;
}

rp++

转载于:https://www.cnblogs.com/wzc521/p/11260885.html

这篇关于插头DP讲解+[BZOJ1814]:Ural 1519 Formula 1(插头DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/614810

相关文章

Java集合中的List超详细讲解

《Java集合中的List超详细讲解》本文详细介绍了Java集合框架中的List接口,包括其在集合中的位置、继承体系、常用操作和代码示例,以及不同实现类(如ArrayList、LinkedList和V... 目录一,List的继承体系二,List的常用操作及代码示例1,创建List实例2,增加元素3,访问元

Python使用国内镜像加速pip安装的方法讲解

《Python使用国内镜像加速pip安装的方法讲解》在Python开发中,pip是一个非常重要的工具,用于安装和管理Python的第三方库,然而,在国内使用pip安装依赖时,往往会因为网络问题而导致速... 目录一、pip 工具简介1. 什么是 pip?2. 什么是 -i 参数?二、国内镜像源的选择三、如何

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》:本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言:1.2定义:1.3衍生用法:1.3Leetcode的实际运用:总结 1.1前言:本文将详

Redis的Zset类型及相关命令详细讲解

《Redis的Zset类型及相关命令详细讲解》:本文主要介绍Redis的Zset类型及相关命令的相关资料,有序集合Zset是一种Redis数据结构,它类似于集合Set,但每个元素都有一个关联的分数... 目录Zset简介ZADDZCARDZCOUNTZRANGEZREVRANGEZRANGEBYSCOREZ

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语,用于确保某个操

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

uva 10154 DP 叠乌龟

题意: 给你几只乌龟,每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析: 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠,状态转移方程: dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]