必威体育Betway必威体育官网
当前位置：首页 > IT技术

插头DP小结

时间:2019-10-02 10:43:15来源:IT技术作者:seo实验室小编阅读:77次「手机版」
　

插头dp

插头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);
}

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);
}

相关阅读

UDP

概述 用户数据保协议（User Datagram Protocol，UDP）是开放系统互联模型（Open System Interconnection，OSI）中传输层协议的一种，是一种保

HostEase香港主机安装WordPress图文教程

想要搭建一个个人网站要怎么做?香港主机和WordPress是最佳搭配。香港主机在国内访问速度快，不用备案，即买即用;而WordPress是流行的

高配便宜又好用的WordPress主机

WordPress是当前全球使用范围最广的CMS内容管理系统，功能强大，扩展性强，安全性高，利用丰富的主题和插件可以搭建个性化、多功能的网站

米拓建站为什么不用wordpress给用户搭建网站？

别笑！这是某网友在悟空问答问米拓建站创始人的问题！以下就直接引用米拓建站创始人的回答：今天有网友问我&ldquo;米拓为什么不使用wor

侠客站群系统V3免费版体验以及WORDPRESS平台实战心得

这几天正有玩站群的欲望，打开早上打开A5一看，侠客站群系统有免费版，于是就在www.xiake5.com/down/v3.rar进行了下载，这么好的事，果断申

赞()
分享到:

猜你喜欢

栏目导航

推荐阅读

热门阅读

seo实验室提供seo优化服务，有网站优化、网站建设、运营推广等需求请联系我们!
Copyright © 2001-2017 .seo实验室 版权所有 网站地图