1. 全栈程序员必看首页

插头DP小结_dp插头接线标准

全栈程序员-用户IM • • 未分类

插头DP小结_dp插头接线标准插头DP一般都是棋盘模型，找路径或者环路最值或者方案数。插头：说白了就是两个联通的格子，一个走向另一个，那么这里就有一个插头。轮廓线：DP逐格DP，那么轮廓线可以分开DP过的格子和未DP的格子。轮廓线的长度明显是m+1。插头垂直于轮廓线。转移：轮廓线在换行的时候要位移，这个画画图就出来了。然后具体问题具体讨论。比如任意多个环路，不考虑方向，那么就是eatthetrees，用最

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

插头DP一般都是棋盘模型，找路径或者环路最值或者方案数。
插头：说白了就是两个联通的格子，一个走向另一个，那么这里就有一个插头。
轮廓线：DP逐格DP，那么轮廓线可以分开DP过的格子和未DP的格子。轮廓线的长度明显是m+1。插头垂直于轮廓线。
转移：
轮廓线在换行的时候要位移，这个画画图就出来了。
然后具体问题具体讨论。比如任意多个环路，不考虑方向，那么就是eat the trees，用最小表示法，因为是任意多个环路，那么插头只有两种，一种是有插头，一种是没插头，具体联通与否我们不管。如果要考虑方向呢？那么插头就有3种，一种是没插头，一种是插头从已DP的指向未DP的，一种是未DP的指向已DP的。
具体实现，有两种思路，一种是括号序列，一种是最小表示法。
括号序列比较快，空间压缩得很好，不过转移太麻烦辣。
最小表示法转移比较好想，就是比较慢，空间比较大。
写法有三种，一种是hash表存取状态，有decode，encode，就是kuangbin那种写法；一种是传统dp写法，位运算取出状态；还有种是claris写法，预处理所有可能状态然后传统DP转移。
kuangbin那个因为位运算比较少，每次都会直接接触到解密的状态，比较直观好想，模式化很强，不过每次都有O(m)的常数用在加密解密上。时空耗费较大，要写hash表，代码较长。
传统DP转移有的是O(1)，有的O(n)，总体来说和上面的差不多。。因为递推转移无效状态比较多。然后代码比较短。缺点就是一堆位运算像我这种傻逼根本看不懂
claris写法太神辣。因为所有状态预处理好了所以状态数很少，因为预处理所以所有转移O(1)，然后代码很短。缺点是我这种傻逼不会预处理。然后还是一堆位运算。并且遇到题目本身状态很多的时候效果不会很好。
我现在只会第一种写法。
下面扔2个例题。
HYSBZ 3125
找一条走过所有格子的环路的方案数。
有的格子只能上下经过，有的只能左右经过，有的不能经过。
这个题我写的括号序列。
插头3种，空插头，左括号，右括号。
然后分9类情况讨论即可。
因为分了9类情况所以代码长爆。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int HASH=10007,STATE=1000010,MAXD=15;
int n,m,ex,ey,code[MAXD];
char maze[MAXD][MAXD];
struct HASHMAP{
int head[HASH],next[STATE],state[STATE],size;
ll f[STATE];
void init()
{
size=0;
memset(head,-1,sizeof head);
}
void push(int st,ll val)
{
int h=st%HASH;
for(int i=head[h];i!=-1;i=next[i])
if(st==state[i])
{
f[i]+=val;
return;
}
f[size]=val;
state[size]=st;
next[size]=head[h];
head[h]=size++;
}
}hm[2];
int encode(int *code,int m)
{
int st=0;
for(int i=0;i<=m;i++)
{
st*=3;
st+=code[i];
}
return st;
}
void decode(int *code,int m,int st)
{
for(int i=m;i>=0;i--)
{
code[i]=st%3;
st/=3;
}
}
void shift(int *code,int m)
{
for(int i=m;i>0;--i)code[i]=code[i-1];
code[0]=0;
}
void dpblank(int i,int j,int cur)
{
for(int k=0;k<hm[cur].size;++k)
{
decode(code,m,hm[cur].state[k]);
int &p=code[j-1],&q=code[j];
if(!p&&!q)
{
if((maze[i+1][j]=='|'||maze[i+1][j]=='.')&&(maze[i][j+1]=='-'||maze[i][j+1]=='.'))
{
p=1,q=2;
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
else if(p&&q)
{
if(p==1&&q==1)
{
int tot=0;
for(int ii=j;ii<=m;++ii)
{
if(code[ii]==1)++tot;
if(code[ii]==2)--tot;
if(tot==0)
{
code[ii]=1;
break;
}
}
p=0,q=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
else if(p==2&&q==2)
{
int tot=0;
for(int ii=j-1;ii>=0;--ii)
{
if(code[ii]==2)++tot;
if(code[ii]==1)--tot;
if(tot==0)
{
code[ii]=2;
break;
}
}
p=0,q=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
else if(p==1&&q==2)
{
if(i==ex&&j==ey)
{
p=0,q=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
else if(p==2&&q==1)
{
p=0,q=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
else
{
if(maze[i][j+1]=='.'||maze[i][j+1]=='-')
{
q=p+q,p=0;
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
if(maze[i+1][j]=='.'||maze[i+1][j]=='|')
{
p=p+q,q=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
}
}
void dpver(int i,int j,int cur)
{
for(int k=0;k<hm[cur].size;++k)
{
decode(code,m,hm[cur].state[k]);
int &p=code[j-1],&q=code[j];
if(p==0&&q)
{
if(maze[i+1][j]=='.'||maze[i+1][j]=='|')
{
p=q,q=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
}
}
void dphor(int i,int j,int cur)
{
for(int k=0;k<hm[cur].size;++k)
{
decode(code,m,hm[cur].state[k]);
int &p=code[j-1],&q=code[j];
if(p&&q==0)
{
if(maze[i][j+1]=='.'||maze[i][j+1]=='-')
{
q=p,p=0;
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
}
}
void dpblock(int i,int j,int cur)
{
for(int k=0;k<hm[cur].size;++k)
{
decode(code,m,hm[cur].state[k]);
code[j-1]=0,code[j]=0;
if(j==m)shift(code,m);
hm[cur^1].push(encode(code,m),hm[cur].f[k]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%s",maze[i]+1);
for(int j=1;j<=m;++j)
if(maze[i][j]=='.')ex=i,ey=j;
}
int cur=0;
ll ans=0;
hm[cur].init();
hm[cur].push(0,1);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
hm[cur^1].init();
if(maze[i][j]=='.')dpblank(i,j,cur);
else if(maze[i][j]=='|')dpver(i,j,cur);
else if(maze[i][j]=='-')dphor(i,j,cur);
else dpblock(i,j,cur);
cur^=1;
}
for(int i=0;i<hm[cur].size;++i)ans+=hm[cur].f[i];
printf("%lld\n",ans);
}

Jetbrains全家桶1年46，售后保障稳定

bzoj2310 parkii
这个题就是弱化的zoj3213
棋盘上的格子有权值。找一条路径使路径上的权值之和最大。
这题我用的最小表示法，需要因为这个是路径不是回路，需要增加独立插头，同事需要增加标志位记录独立插头个数。要使独立插头个数小于等于2.具体实现的时候把标志位也压进状态里面。
最小表示法就相对好讨论一些。因为括号序列的性质，轮廓线上m+1个点最多只有m/2个不同的联通块，根据这个压位DP。
如果左插头和上插头都有，那么右插头和下插头就没有了。有以下2种情况：
1、如果左插头和上插头都有且不在一个联通块内，就连接他们。连接还要重标号最小表示。因为以前左插头所在联通块和上插头所在联通块不是一个，现在要暴力修改。
2、如果左插头和上插头都有且在一个联通块内，就不管了。
如果左插头和上插头只有一个，那么就有以下3种情况：
1、这个插头可以延续一个右插头
2、这个插头可以延续一个下插头
3、这个插头可以延续一个独立插头
注意延续一个右/下插头不要走出棋盘了，注意延续独立插头的前提是轮廓线上独立插头数量小于2
如果左插头和上插头都没有，那么就有以下3种情况：
1、右插头和下插头都得有，现在他们俩在一个联通块内。注意这样不要走出棋盘了。
2、左插头变成独立插头再延续一个右插头。注意延续独立插头的前提是轮廓线上独立插头数量小于2。
3、右插头变成独立插头再延续一个左插头。注意延续独立插头的前提是轮廓线上独立插头数量小于2。
这样就讨论完了。注意换行的时候状态要位移。如果用括号序列分类有16种= =这个我太傻逼了不会做。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int HASH=10007,STATE=1000010,MAXD=15;
int n,m,num,code[MAXD],ch[MAXD],maze[105][MAXD];
struct HASHMAP{
int head[HASH],next[STATE],state[STATE],f[STATE],size;
void init()
{
size=0;
memset(head,-1,sizeof head);
}
void push(int st,int val)
{
int h=st%HASH;
for(int i=head[h];~i;i=next[i])
if(st==state[i])
{
f[i]=max(f[i],val);
return;
}
f[size]=val;
state[size]=st;
next[size]=head[h];
head[h]=size++;
}
}hm[2];
int encode(int *code,int m)
{
int st=0,cnt=1;
memset(ch,-1,sizeof ch);
ch[0]=0;
for(int i=0;i<=m;++i)
{
if(ch[code[i]]==-1)ch[code[i]]=cnt++;
code[i]=ch[code[i]];
st<<=3;
st|=code[i];
}
st<<=3;
st|=num;
return st;
}
void decode(int *code,int m,int st)
{
num=st&7;
st>>=3;
for(int i=m;i>=0;--i)
{
code[i]=st&7;
st>>=3;
}
}
void dp(int i,int j,int cur)
{
for(int k=0;k<hm[cur].size;++k)
{
decode(code,m,hm[cur].state[k]);
int p=code[j-1],q=code[j];
if(p&&q)
{
if(p!=q)
{
for(int ii=0;ii<=m;++ii)
if(code[ii]==q)code[ii]=p;
code[j-1]=code[j]=0;
hm[cur^1].push(encode(code,j==m?m-1:m),hm[cur].f[k]+maze[i][j]);
}
}
else if(p||q)
{
if(j+1<=m)
{
code[j]=p+q,code[j-1]=0;
hm[cur^1].push(encode(code,m),hm[cur].f[k]+maze[i][j]);
}
if(i+1<=n)
{
code[j-1]=p+q,code[j]=0;
hm[cur^1].push(encode(code,j==m?m-1:m),hm[cur].f[k]+maze[i][j]);
}
if(num<2)
{
++num;
code[j-1]=code[j]=0;
hm[cur^1].push(encode(code,j==m?m-1:m),hm[cur].f[k]+maze[i][j]);
}
}
else
{
code[j-1]=code[j]=0;
hm[cur^1].push(encode(code,j==m?m-1:m),hm[cur].f[k]);
if(j+1<=m&&i+1<=n)
{
code[j-1]=code[j]=13;
hm[cur^1].push(encode(code,m),hm[cur].f[k]+maze[i][j]);
}
if(num<2)
{
++num;
if(j+1<=m)
{
code[j-1]=0,code[j]=13;
hm[cur^1].push(encode(code,m),hm[cur].f[k]+maze[i][j]);
}
if(i+1<=n)
{
code[j-1]=13,code[j]=0;
hm[cur^1].push(encode(code,j==m?m-1:m),hm[cur].f[k]+maze[i][j]);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&maze[i][j]);
int cur=0,ans=-999999999;
hm[cur].init();
hm[cur].push(0,0);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
ans=max(ans,maze[i][j]);
hm[cur^1].init();
dp(i,j,cur);
cur^=1;
}
for(int i=0;i<hm[cur].size;++i)ans=max(ans,hm[cur].f[i]);
printf("%d\n",ans);
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/219603.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0


相关推荐

  • maven学习系列——（四）maven仓库

    maven学习系列——（四）maven仓库

    这一篇学习和整理maven仓库的一些知识点！

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年2月25日
  • insmod失败_ins玩不了

    insmod失败_ins玩不了

    insmod失败_ins玩不了cmemk:versionmagic’2.6.32mod_unloadmodversionsARMv7’shouldbe’2.6.32preemptmod_unloadmodversionsARMv7’如上所示，是配置没有匹配．比如上面这个要配置为preempt，抢占式的．特此记录下．

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年11月1日
  • Sqoop问题解决：运行报错java.lang.RuntimeException: Could not load db driver class: com.mysql.jdbc.Driver

    Sqoop问题解决：运行报错java.lang.RuntimeException: Could not load db driver class: com.mysql.jdbc.Driver

    Sqoop问题解决：运行报错java.lang.RuntimeException: Could not load db driver class: com.mysql.jdbc.DriverSqoop问题解决：运行报错报错信息：java.lang.RuntimeException:Couldnotloaddbdriverclass:com.mysql.jdbc.Driver原因分析：未将mysql关系型数据库驱动包放到sqoop/lib目录下解决方法：将mysql关系型数据库驱动包放到sqoop/lib目录下这里需要下载mysql关系型数据库驱动包放到本地/opt/software/下mysql依赖包下载链接：https://pan.baidu.com/s

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年7月25日
  • STM32编程怎么入门，聊聊我的入门经历

    STM32编程怎么入门，聊聊我的入门经历

    STM32编程怎么入门，聊聊我的入门经历我第一次接触STM32大概是在8,9年前。当时刚出来工作不久，在此之前主要用stc和nxp的单片机比较多。那个时候还没有固件库开发的概念，基本都是配置寄存器去使用单片机外设资源。虽然说用起来比较麻烦，但是执行的效率也相对高一点，习惯了也挺好用。新项目比较复杂一点，一个老工程师建议我用stm32的单片机做效率比较高。听大佬的话照做是一个小菜鸟的基本素养，所以我选了stm32。对于学习这块，我也比较舍得（当时月薪只有1.8K），毫不犹豫花了几百大洋购买了一套stm32开发板。学习一款

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年9月7日
  • javascript 匿名函数_定义匿名函数的关键字是

    javascript 匿名函数_定义匿名函数的关键字是

    javascript 匿名函数_定义匿名函数的关键字是JavaScript匿名函数介绍：匿名函数顾名思义指的是没有名字的函数，在实际开发中使用的频率非常高。本文将对此介绍。

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年10月4日
  • 简述面向对象思想_简述面向对象程序设计的特点

    简述面向对象思想_简述面向对象程序设计的特点

    简述面向对象思想_简述面向对象程序设计的特点简述Java中的面向对象（OOP）思想Java是一种面向对象的语言，那么什么是面向对象（ObjectOrientedProgramming）？首先，什么是对象(Object)？Java中有一种

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年8月5日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号