博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
[原创]插头DP小结（ACM by kuangbin）
阅读量：7044 次
发布时间：2019-06-28

本文共 21515 字，大约阅读时间需要 71 分钟。

这几天学习了一下插头DP，刷了11道题。对插头DP有了点理解。插头DP就先告一段落吧！ 后面还有插头DP的广义路径和其它复杂应用，以后有机会再补上吧！

      kuangbin

 

 

首先入门推荐的还是cdq的论文

上面的论文关于插头和轮廓线等概念讲得很清楚。而且关于插头DP的精髓也讲得很透了。

插头DP其实就是每格进行状态转移。

看懂原理和写代码还是有段距离的，可以结合代码去加深理解原理。同时形成适合自己风格的代码模板。

 

  此题是比较基础的入门题。

多条回路，求回路数问题。格子有障碍格子和非障碍格子两种。

：

HDU 1693 
#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int HASH=10007;const int STATE=1000010;//状态数const int MAXD=15;int N,M;int code[MAXD],maze[MAXD][MAXD];struct HASHMAP{    int head[HASH],next[STATE],state[STATE],size;    long long f[STATE];    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    void push(int st,long long ans)    {        int i,h=st%HASH;        for(i=head[h];i!=-1;i=next[i])          if(st==state[i])          {              f[i]+=ans;              return;          }        f[size]=ans;        state[size]=st;        next[size]=head[h];        head[h]=size++;    }}hm[2];void decode(int *code,int m,int st){    int i;    for(i=m;i>=0;i--)    {        code[i]=st&1;        st>>=1;    }}int encode(int *code,int m){    int i,st=0;    for(int i=0;i<=m;i++)    {        st<<=1;        st|=code[i];    }    return st;}void init(){    int i,j;    scanf("%d%d",&N,&M);    for(i=1;i<=N;i++)      for(int j=1;j<=M;j++)        scanf("%d",&maze[i][j]);    for(int i=1;i<=N;i++)maze[i][M+1]=0;//边界补0    for(int i=1;i<=M;i++)maze[N+1][i]=0;}void shift(int *code,int m)//换行的时候移位{    int i;    for(i=m;i>0;i--)      code[i]=code[i-1];    code[0]=0;}void dpblank(int i,int j,int cur){    int k,left,up;    for(k=0;k
          
            00        {            code[j-1]=code[j]=0;            if(j==M)shift(code,M);            hm[cur^1].push(encode(code,M),hm[cur].f[k]);        }        else if(left||up)//01 或 10        {            if(maze[i][j+1])            {                code[j-1]=0;                code[j]=1;                hm[cur^1].push(encode(code,M),hm[cur].f[k]);            }            if(maze[i+1][j])            {                code[j-1]=1;                code[j]=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+1][j])            {                code[j]=code[j-1]=1;                hm[cur^1].push(encode(code,M),hm[cur].f[k]);            }        }    }}void dpblock(int i,int j,int cur){    int k;    for(k=0;k

 

  和论文上的同一道题。此题是求单回路数问题，和上面的一题在状态转移时有点不同。就是形成回路一定要在最后一个非障碍格子。

我的代码是用最小表示法做的。

：

ural 1519 
/*最小表示法*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXD=15;const int HASH=30007;const int STATE=1000010;int N,M;int maze[MAXD][MAXD];int code[MAXD];int ch[MAXD];//最小表示法使用int ex,ey;//最后一个非障碍格子的坐标struct HASHMAP{    int head[HASH],next[STATE],size;    long long state[STATE];    long long f[STATE];    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    void push(long long st,long long ans)    {        int i;        int h=st%HASH;        for(i=head[h];i!=-1;i=next[i])//这里要注意是next          if(state[i]==st)          {              f[i]+=ans;              return;          }        state[size]=st;        f[size]=ans;        next[size]=head[h];        head[h]=size++;    }}hm[2];void decode(int *code,int m,long long  st){    for(int i=m;i>=0;i--)    {        code[i]=st&7;        st>>=3;    }}long long encode(int *code,int m)//最小表示法{    int cnt=1;    memset(ch,-1,sizeof(ch));    ch[0]=0;    long long st=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];    }    return st;}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){    int k,left,up;    for(k=0;k

 

 

 

  此题也是单回路数问题。但是格子有了三种：障碍格子，必走格子和选择性经过格子。这样导致最后一个非障碍格子不确定。所以增加一个标志位来记录是否形成回路。

：

FZU 1977 
/*FZU 1977简单回路数问题，N*M(1<=N,M<=12)的方格中有障碍点，必走点和非必走点因为回路只有一条，而形成回路的最后一个点又是不确定的。所以额外增加一个标志位来记录是否形成回路。如果已经形成回路，而后面又遇到插头或者必须走的点，则该方案不合法G++ 375ms*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXD=15;const int HASH=10007;const int STATE=100010;int N,M;int code[MAXD];int maze[MAXD][MAXD];//0表示障碍点，1表示非必走点，2表示必走点int ch[MAXD];int isend;//是否形成回路标记位struct HASHMAP{    int head[HASH],next[STATE],size;    long long state[STATE],f[STATE];    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    void push(long long st,long long ans)    {        int i,h=st%HASH;        for(i=head[h];i!=-1;i=next[i])            if(state[i]==st)            {                f[i]+=ans;                return;            }        state[size]=st;        f[size]=ans;        next[size]=head[h];        head[h]=size++;    }}hm[2];void decode(int *code,int m,long long st)//注意要增加一个isend标记位{    for(int i=m;i>=0;i--)    {        code[i]=st&7;        st>>=3;    }    isend=st&1;//isend标记位在st的最高一位}long long encode(int *code,int m)//增加isend标记位{    long long st=isend;//最高位    int 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];    }    return st;}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){    int k,left,up;    for(k=0;k

 

 

 

 

  每个格子之间的墙壁有个花费，求用一个环经过每个格子仅一次的最小花费。此题不求方案数，只需要取最小值即可。而且所有格子都是非障碍格子，这样和Ural 1519就和类似了，而且更加简单。

：

 

HDU 1964 
/*HDU 1964 Pipes插头DP每个格子之间的墙壁有一个花费，求用一个环经过每个格子一次的最小花费G++ 46ms*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXD=15;const int HASH=10007;const int STATE=1000010;struct Node{    int down,right;//每个格子下边和右边墙的花费}node[MAXD][MAXD];int N,M;int maze[MAXD][MAXD];int code[MAXD];int ch[MAXD];//最小表示法使用int ex,ey;//最后一个非障碍格子的坐标struct HASHMAP{    int head[HASH],next[STATE],size;    int dp[STATE];    long long state[STATE];//最小表示法，最大是8^11,就是2^33,所以用long long    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    void push(long long st,int ans)    {        int i,h=st%HASH;        for(i=head[h];i!=-1;i=next[i])           if(state[i]==st)           {               if(dp[i]>ans)dp[i]=ans;               return;           }        dp[size]=ans;        state[size]=st;        next[size]=head[h];        head[h]=size++;    }}hm[2];void decode(int *code,int m,long long st){    for(int i=m;i>=0;i--)    {        code[i]=st&7;        st>>=3;    }}long long encode(int *code,int m){    int cnt=1;    memset(ch,-1,sizeof(ch));    ch[0]=0;    long long st=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];    }    return st;}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){    int k,left,up;    for(k=0;k

 

 

    从左上角走到右下角，每个格子有个分数。每个格子最多经过一次，可以不经过，求最大分数。 模板修改下就出来了。

：

HDU 3377 
/*HDU 3377从左上角走到右下角。每个格子有个分数。每个格子只能经过一次，可以不经过求最大分数G++ 140ms*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXD=15;const int HASH=10007;const int STATE=1000010;int N,M;int maze[MAXD][MAXD];int score[MAXD][MAXD];int code[MAXD];int ch[MAXD];struct HASHMAP{    int head[HASH],state[STATE],next[STATE],size;    int dp[STATE];    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    void push(int st,int ans)    {        int i,h=st%HASH;        for(i=head[h];i!=-1;i=next[i])           if(state[i]==st)           {               if(dp[i]
          
           =0;i--)    {        code[i]=st&7;        st>>=3;    }}int encode(int *code,int m){    int cnt=1;    memset(ch,-1,sizeof(ch));    ch[0]=0;    int st=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];    }    return st;}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){    int k,left,up;    for(k=0;k

 

 

 

 

   楼教主的男人八题之一。从左下角走到右下角，每个非障碍格子仅走一次的方法数。一种方法是在后面增加两行转换成回路问题，这样就和ural 1519一样了。也可以不增加行，直接特殊处理下即可。

：

POJ 1739 
/*POJ 1739题目意思就是从左下角走到右下角，每个非障碍格子都走一遍的方法数转换成回路问题。在最后加两行   .########.   ..........这样就转成回路问题了，就和URAL 1519 一样的做法了G++ 47ms*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXD=15;const int HASH=10007;const int STATE=1000010;int N,M;int maze[MAXD][MAXD];int code[MAXD];int ch[MAXD];//最小表示法使用int ex,ey;//最后一个非障碍格子的坐标struct HASHMAP{    int head[HASH],next[STATE],size;    long long state[STATE],f[STATE];    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    void push(long long st,long long ans)    {        int i;        int h=st%HASH;        for(i=head[h];i!=-1;i=next[i])          if(state[i]==st)          {              f[i]+=ans;              return;          }        state[size]=st;        f[size]=ans;        next[size]=head[h];        head[h]=size++;    }}hm[2];void decode(int *code,int m,long long st){    for(int i=m;i>=0;i--)    {        code[i]=st&7;        st>>=3;    }}long long encode(int *code,int m){    int cnt=1;    memset(ch,-1,sizeof(ch));    ch[0]=0;    long long st=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];    }    return st;}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){    int k,left,up;    for(k=0;k

 

POJ 1739 
/*POJ 1739不增加行。起点和终点特殊处理G++ 47ms*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXD=15;const int HASH=10007;const int STATE=1000010;int N,M;int maze[MAXD][MAXD];int code[MAXD];int ch[MAXD];//最小表示法使用int ex,ey;//最后一个非障碍格子的坐标struct HASHMAP{    int head[HASH],next[STATE],size;    long long state[STATE],f[STATE];    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    void push(long long st,long long ans)    {        int i;        int h=st%HASH;        for(i=head[h];i!=-1;i=next[i])          if(state[i]==st)          {              f[i]+=ans;              return;          }        state[size]=st;        f[size]=ans;        next[size]=head[h];        head[h]=size++;    }}hm[2];void decode(int *code,int m,long long st){    for(int i=m;i>=0;i--)    {        code[i]=st&7;        st>>=3;    }}long long encode(int *code,int m){    int cnt=1;    memset(ch,-1,sizeof(ch));    ch[0]=0;    long long st=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];    }    return st;}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){    int k,left,up;    for(k=0;k

 

 

 

 

   格子中有两个2，两个3.求把两个2连起来，两个3连起来。求经过总的格子数的总和减2.  两条路径不能交叉。有障碍格子。非障碍格子最多经过一次。插头出需要记录三种状态：没有插头、2号插头、3号插头。可以用三进制。但是考虑到4进制更加高效，我用的四进制做的。

：

 

POJ 3133 
/*POJ 3133连接2的插头为2，连接3的插头为3没有插头为0用四进制表示（四进制比三进制高效）G++ 391ms*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXD=15;const int HASH=10007;const int STATE=1000010;int N,M;int maze[MAXD][MAXD];//0表示障碍，1是非障碍，2和3int code[MAXD];//0表示没有插头,2表示和插头2相连，3表示和插头3相连struct HASHMAP{    int head[HASH],next[STATE],size;    int state[STATE];    int dp[STATE];    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    void push(int st,int ans)    {        int i,h=st%HASH;        for(i=head[h];i!=-1;i=next[i])          if(state[i]==st)          {              if(dp[i]>ans)dp[i]=ans;              return;          }        state[size]=st;        dp[size]=ans;        next[size]=head[h];        head[h]=size++;    }}hm[2];void decode(int *code,int m,int st)//四进制{    int i;    for(int i=m;i>=0;i--)    {        code[i]=(st&3);        st>>=2;    }}int encode(int *code,int m){    int i;    int st=0;    for(int i=0;i<=m;i++)    {        st<<=2;        st|=code[i];    }    return st;}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){    int k,left,up;    for(k=0;k
          
           0)ans-=2;    printf("%d\n",ans);}int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    while(scanf("%d%d",&N,&M))    {        if(N==0&&M==0)break;        init();        solve();    }    return 0;}

 

 

 

  和HDU 1693一样，求多回路问题。但是四边形换成了六边行。难度相应提高了。做的方法是一样的。我是倒过来，按照列来转移的，稍微简单一下。按照行可以做，但是讨论比较多，我没有去尝试。

：

ZOJ 3466 
/*ZOJ 3466C++ 3850ms 62768K原来ZOJ中的long long要用%lld输出啊对ZOJ不熟悉啊，被坑了好久*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int HASH=10007;const int STATE=2000010;const int MAXD=32;int N,M;int code[MAXD],maze[MAXD][MAXD];struct HASHMAP{    int head[HASH],next[STATE],state[STATE],size;    long long f[STATE];    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    void push(int st,long long ans)    {        int i,h=st%HASH;        for(i=head[h];i!=-1;i=next[i])          if(st==state[i])          {              f[i]+=ans;              return;          }        f[size]=ans;        state[size]=st;        next[size]=head[h];        head[h]=size++;    }}hm[2];void decode(int *code,int m,int st){    int i;    for(i=m;i>=0;i--)    {        code[i]=st&1;        st>>=1;    }}int encode(int *code,int m){    int i,st=0;    for(i=0;i<=m;i++)    {        st<<=1;        st|=code[i];    }    return st;}void init(){    N=8;//倒过来，8行    int t;    scanf("%d",&t);    memset(maze,0,sizeof(maze));    for(int i=1;i<=N;i++)      for(int j=1;j<=M;j++)        maze[i][j]=1;    char str[10];    while(t--)    {        scanf("%s",&str);        maze[str[1]-'A'+1][M-(str[0]-'A')]=0;    }}void shift(int *code,int m)//偶数行换奇数行的时候要变化{    for(int i=m;i>1;i--)      code[i]=code[i-2];    code[0]=0;    code[1]=0;}void dpblank(int i,int j,int cur){    int k,left,up1,up2;    int t1,t2;    if(i%2==0)t1=j,t2=j+1;    else t1=j-1,t2=j;    for(k=0;k

 

 

 

 

 

   这题数据很大。求左上角到右下角的路径数。经过所以格子一次。要用矩阵加速。由于每一列都是一样的，状态转移就相同。用插头DP求出列与列之间的状态转移，然后用矩阵乘法。这题比较难

：

ZOJ 3256 
/*ZOJ 3256N*M(2<=N<=7,1<=M<=10^9)的方格，问从左上角的格子到左下角的格子，而且仅经过所有格子一次的路径数插头DP+矩阵加速对于一个图的邻接矩阵的N次方，其中(i,j)位置上的元素表示点i经过N步到达点ｊ的方案数*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int STATE=1010;const int HASH=419;//这个小一点，效率高const int MOD=7777777;int N,M;int D;int code[10];int ch[10];int g[200][200];//状态转移图struct Matrix{    int n,m;    int mat[200][200];};Matrix mul(Matrix a,Matrix b)//矩阵相乘，要保证a的列数和b的行数相等{    Matrix ret;    ret.n=a.n;    ret.m=b.m;    long long sum;    for(int i=0;i
          
           >=1;    }    return ret;}struct HASHMAP{    int head[HASH],next[STATE],size;    int state[STATE];    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    int push(int st)    {        int i,h=st%HASH;        for(i=head[h];i!=-1;i=next[i])           if(state[i]==st)              return i;        state[size]=st;        next[size]=head[h];        head[h]=size++;        return size-1;    }}hm;void decode(int *code,int n,int st){    for(int i=n-1;i>=0;i--)    {        code[i]=st&3;        st>>=2;    }}int encode(int *code,int n){    int cnt=1;    memset(ch,-1,sizeof(ch));    ch[0]=0;    int st=0;    for(int i=0;i
           
            0) { for(int j=0;j
            
             0)code[i]=code[k],code[k]=0; else code[i]=code[k]=N+(cnt++); } flag=0; } } if(flag!=0)return false; return true;}struct Node{ int g[200][200]; int D;}node[20];//打表之用void init(){ if(node[N].D!=0) { memcpy(g,node[N].g,sizeof(node[N].g)); D=node[N].D; return; } int st,nst; hm.init(); memset(code,0,sizeof(code)); code[0]=code[N-1]=1; hm.push(0); hm.push(encode(code,N)); memset(g,0,sizeof(g)); for(int i=1;i

 

 

 

 

   此题求简单路径。得到最大的分数。

用最小表示法，需要增加标志位记录独立插头个数。要使独立插头个数小于等于2.

：

ZOJ 3213 
/*ZOJ 3213*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXD=15;const int HASH=10007;const int STATE=1000010;int N,M;int maze[MAXD][MAXD];int code[MAXD];int ch[MAXD];int num;//独立插头的个数int ans;//答案struct HASHMAP{    int head[HASH],next[STATE],size;    int state[STATE],dp[STATE];    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    void push(int st,int ans)    {        int i,h=st%HASH;        for(i=head[h];i!=-1;i=next[i])          if(state[i]==st)          {              if(dp[i]
          
           >=3;    for(int i=m;i>=0;i--)    {        code[i]=st&7;        st>>=3;    }}int encode(int *code,int m){    int cnt=1;    memset(ch,-1,sizeof(ch));    ch[0]=0;    int st=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 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){    int k,left,up;    for(k=0;k
           
            ans)ans=maze[i][j]; }}void solve(){ int i,j,cur=0; hm[cur].init(); hm[cur].push(0,0); for(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 dpblock(i,j,cur); cur^=1; } for(i=0;i
            
             ans) ans=hm[cur].dp[i]; printf("%d\n",ans);}int main(){ // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int T; scanf("%d",&T); while(T--) { init(); solve(); } return 0;}/*Sample Input21 1101 25 0Sample Output105*/

 

 

 

 

 

   这是天津网络赛的题目。求K个回路的方案数。而且不能是环套环。

增加个标志位来记录形成的回路个数。而且注意避免环套环的情况。

：

 

HDU 4285 
/*HDU 4285要形成刚好K条回路的方法数要避免环套环的情况。所以形成回路时，要保证两边的插头数是偶数G++ 11265ms  11820KC++ 10656ms  11764K*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXD=15;const int STATE=1000010;const int HASH=300007;//这个大一点可以防止TLE,但是容易MLEconst int MOD=1000000007;int N,M,K;int maze[MAXD][MAXD];int code[MAXD];int ch[MAXD];int num;//圈的个数struct HASHMAP{    int head[HASH],next[STATE],size;    long long state[STATE];    int f[STATE];    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    void push(long long st,int ans)    {        int i;        int h=st%HASH;        for(i=head[h];i!=-1;i=next[i])          if(state[i]==st)          {              f[i]+=ans;              f[i]%=MOD;              return;          }        state[size]=st;        f[size]=ans;        next[size]=head[h];        head[h]=size++;    }}hm[2];void decode(int *code,int m,long long  st){    num=st&63;    st>>=6;    for(int i=m;i>=0;i--)    {        code[i]=st&7;        st>>=3;    }}long long encode(int *code,int m)//最小表示法{    int cnt=1;    memset(ch,-1,sizeof(ch));    ch[0]=0;    long long st=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<<=6;    st|=num;    return st;}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){    int k,left,up;    for(k=0;k
          
           =K)continue;                int t=0;                //要避免环套环的情况，需要两边插头数为偶数                for(int p=0;p
HDU4285 
/*HDU  4285要形成刚好K条回路的方法数要避免环套环的情况。所以形成回路时，要保证两边的插头数是偶数G++ 11765ms  12560KC++  11656ms 12504K*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXD=15;const int STATE=1000010;const int HASH=100007;const int MOD=1000000007;int N,M,K;int maze[MAXD][MAXD];int code[MAXD];int ch[MAXD];struct HASHMAP{    int head[HASH],next[STATE],size;    long long state[STATE];    int f[STATE];    int cir[STATE];//形成的圈的个数    void init()    {        size=0;        memset(head,-1,sizeof(head));    }    void push(long long st,int ans,int _cir)    {        int i,h=st%HASH;        for(i=head[h];i!=-1;i=next[i])          if(state[i]==st&&cir[i]==_cir)          {              f[i]+=ans;              f[i]%=MOD;              return;          }        state[size]=st;        f[size]=ans;        cir[size]=_cir;        next[size]=head[h];        head[h]=size++;    }}hm[2];void decode(int *code,int m,long long  st){    for(int i=m;i>=0;i--)    {        code[i]=st&7;        st>>=3;    }}long long encode(int *code,int m)//最小表示法{    int cnt=1;    memset(ch,-1,sizeof(ch));    ch[0]=0;    long long st=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];    }    return st;}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){    int k,left,up;    for(k=0;k
          
           =K)continue;                int t=0;                for(int p=0;p

 

 

 

上面各题的代码，我都是用一样的模板写的，写的风格都是一致的。插头DP写起来比较难。而且容易写错。更加复杂的插头DP真的很难想到。

但是插头DP还是很美妙的。更多插头DP的题目等我做了会更新上去的。

持续更新中......

2012-10-2   by kuangbin

转载地址：http://cuzol.baihongyu.com/

你可能感兴趣的文章
【直播回顾及资料下载】Fusion Design - 企业级UI解决方案揭秘
查看>>
Meta标签大集合
查看>>
Gitea 1.8.0 发布，组织可设置为公开、内部与私有状态
查看>>
Apache Subversion 1.12.0 发布，版本控制系统
查看>>
MyBatis Dynamic SQL 1.1.1 发布，生成动态 SQL 的框架
查看>>
Opera 60 正式发布，代号 Reborn 3
查看>>
《Java8实战》-第十章笔记（用Optional取代null）
查看>>
IPTables简介四——目标（动作）
查看>>
Andrew Ng机器学习课程笔记--week1（机器学习介绍及线性回归）
查看>>
【nodejs】让nodejs像后端mvc框架（asp.net mvc）一样处理请求--请求处理结果适配篇（7/8）...
查看>>
用Python告诉你，现在的房租有多高？
查看>>
CSS3动画表单
查看>>
Spring Data JPA 持久层开发
查看>>
轻松 get 报表模糊查询技能
查看>>
SparkSQL实践与优化
查看>>
团队绩效考核的思考
查看>>
死磕 Elasticsearch 方法论：普通程序员高效精进的 10 大狠招！（Elasticsearch教程序章）|MVP讲堂...
查看>>
PostgreSQL 10.1 手册_部分 II. SQL 语言_第 10 章 类型转换_10.6. SELECT 输出列
查看>>
使用Java类加载SpringBoot、SpringCloud配置文件
查看>>
Java枚举
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-02-07 04:11:28   当前IP: 3.144.232.21   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我