好学易懂从零开始的插头DP（三）

写在前面

这篇文章主要是介绍一些括号表示法和简单回路的基本变化，下一篇会是一些非回路（最小表示），毒瘤状态（正wa着所以咕着），结合矩阵乘法加速等一些复杂应用。下下篇应该会是结尾，介绍一些除了路径问题以外的应用。这几篇题目的部分不会讲的非常详细，主要是自己思考，所以只会说大体思路。

FZU 1977（这个OJ要用I64d不能lld，不然wa）

题目大意：

n*m的格子，有些格子不能走，有些必须走，有些可以走。问，合法回路个数。

题目分析：

对于基本模板，有两个地方要处理。
一是插头转移，转移的时候不仅要考虑插头情况，还要考虑格点情况，这个题目格点情况有些变化。
二是终止格点不再确定。我的思路是最后一个必须走的点和它之后的可走的点都可以做终止格点，终止条件是只有一个左括号和右括号。

代码如下：

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<cstring>
  4 using namespace std;
  5 const long long hs=10007;
  6 long long n,m,ex,ey,now,last,ans;
  7 long long a[13][13],b[13][13],head[100010],nex[100010],que[2][100010],val[2][100010],cnt[2],inc[13];
  8 void init()
  9 {
 10     scanf("%lld%lld",&n,&m);
 11     memset(a,0,sizeof(a));
 12     memset(b,0,sizeof(b));
 13     memset(head,0,sizeof(head));    
 14     memset(nex,0,sizeof(nex));     
 15     memset(que,0,sizeof(que));
 16     memset(val,0,sizeof(val));
 17     memset(cnt,0,sizeof(cnt));
 18     memset(inc,0,sizeof(inc)); 
 19     ans=0;
 20     for (int i=1;i<=n;i++)
 21     {
 22         for (int j=1;j<=m;j++)
 23         {
 24             char ch=getchar();
 25             while (ch!='*'&&ch!='O'&&ch!='X') ch=getchar();
 26             if (ch=='X') a[i][j]=0;
 27             else if (ch=='*') a[i][j]=2;
 28             else 
 29             {
 30                 a[i][j]=1;
 31                 ex=i;
 32                 ey=j;
 33             }
 34         }
 35     }
 36     inc[0]=1;
 37     for(int i=1;i<=13;i++)
 38     {
 39        inc[i]=inc[i-1]<<2;
 40     }
 41     for (int i=n;i>=1;i--)
 42     {
 43         for (int j=m;j>=1;j--)
 44         {
 45             if (a[i][j]!=0) b[i][j]=1;
 46             if (i==ex&&j==ey) return;
 47         }
 48     }
 49 }
 50 inline void insert(long long bit,long long num)
 51 {
 52    long long u=bit%hs+1;
 53    for(int i=head[u];i;i=nex[i])
 54    {
 55        if(que[now][i]==bit)
 56        {
 57            val[now][i]+=num;
 58            return;
 59        }
 60    }
 61    nex[++cnt[now]]=head[u];
 62    head[u]=cnt[now];
 63    que[now][cnt[now]]=bit;
 64    val[now][cnt[now]]=num;
 65 }
 66 inline void solve()
 67 {
 68     cnt[now]=1; 
 69     val[now][1]=1; 
 70     que[now][1]=0;
 71     for(int i=1;i<=n;i++)
 72     {
 73         for(int j=1;j<=cnt[now];j++)
 74         {
 75             que[now][j]<<=2;
 76         }
 77            for(int j=1;j<=m;++j)
 78            {
 79             memset(head,0,sizeof(head));
 80             last=now; now^=1;
 81                cnt[now]=0;
 82             for(int k=1;k<=cnt[last];++k)
 83             {
 84                    long long bit=que[last][k],num=val[last][k];
 85                    long long b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4;
 86                    if(a[i][j]==0)
 87                    {
 88                    if(!b1&&!b2) insert(bit,num);
 89                    }
 90                    else if(!b1&&!b2)
 91                 {
 92                     if (a[i][j]==2) insert(bit,num);
 93                        if(a[i+1][j]&&a[i][j+1]) insert(bit+inc[j-1]+inc[j]*2,num);
 94                    }
 95                 else if(!b1&&b2)
 96                 {
 97                        if(a[i][j+1]) insert(bit,num);
 98                        if(a[i+1][j]) insert(bit-inc[j]*b2+inc[j-1]*b2,num);
 99                    }
100                 else if(b1&&!b2)
101                 {
102                        if(a[i+1][j]) insert(bit,num);
103                        if(a[i][j+1]) insert(bit-inc[j-1]*b1+inc[j]*b1,num);
104                    }
105                 else if(b1==1&&b2==1)
106                 {
107                        int flag=1;
108                        for(int l=j+1;l<=m;++l)
109                     {
110                            if((bit>>(l*2))%4==1) flag++;
111                            if((bit>>(l*2))%4==2) flag--;
112                            if(!flag)
113                         {
114                                insert(bit-inc[j]-inc[j-1]-inc[l],num);
115                                break;
116                            }
117                        }
118                    }
119                 else if(b1==2&&b2==2)
120                 {
121                        int flag=1;
122                        for(int l=j-2;l>=0;--l)
123                        {
124                            if((bit>>(l*2))%4==1) flag--;
125                            if((bit>>(l*2))%4==2) flag++;
126                            if(!flag)
127                         {
128                                insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
129                                break;
130                            }
131                        }
132                    }
133                 else if(b1==2&&b2==1) insert(bit-inc[j-1]*2-inc[j],num);
134                     else if (bit-inc[j-1]-inc[j]-inc[j]==0&&b[i][j]==1) ans=ans+num;
135                }
136            }
137        }
138 }
139 int main()
140 {
141     int t;
142     scanf("%lld",&t);
143     for (int i=1;i<=t;i++)
144     {
145         init();
146         solve();
147         printf("Case %d: %lld
",i,ans);
148     }
149     return 0;
150 }

View Code of FZU 1977

P3190 [HNOI2007]神奇游乐园

题目大意：

n*m的格子（n<=100,m<=6)，每个格子有一个权值。求最大权回路的权值。

题目分析：

现在我们已经会处理可选格点了。这里全部都是可选格点。再加上一个很简单的变化，状态改为记录最大权。同时处理插头的时候判断要不要加上这个点的权值。

代码如下：

  1 #include<cstdio>
  2 #include<cstring>
  3 using namespace std;
  4 const long long hs=299987;
  5 long long n,m,ex,ey,now,last,ans;
  6 long long a[101][8],head[300000],next[2<<8],que[2][2<<8],val[2][2<<8],cnt[2],inc[10];
  7 void init()
  8 {
  9     scanf("%lld%lld",&n,&m);
 10     for (int i=1;i<=n;i++)
 11     {
 12         for (int j=1;j<=m;j++)
 13         {
 14             scanf("%lld",&a[i][j]);
 15         }
 16     }
 17     inc[0]=1;
 18     for(int i=1;i<=8;i++)
 19     {
 20        inc[i]=inc[i-1]<<2;
 21     }
 22     ans=-(n*m*1001);
 23 }
 24 inline void insert(long long bit,long long num)
 25 {
 26    long long u=bit%hs+1;
 27    for(int i=head[u];i;i=next[i])
 28    {
 29        if(que[now][i]==bit)
 30        {
 31            if (val[now][i]<num) val[now][i]=num;
 32            return;
 33        }
 34    }
 35    next[++cnt[now]]=head[u];
 36    head[u]=cnt[now];
 37    que[now][cnt[now]]=bit;
 38    val[now][cnt[now]]=num;
 39 }
 40 inline void work()
 41 {
 42     cnt[now]=1; 
 43     val[now][1]=0; 
 44     que[now][1]=0;
 45     for(int i=1;i<=n;i++)
 46     {
 47         for(int j=1;j<=cnt[now];j++)
 48         {
 49             que[now][j]<<=2;
 50         }
 51            for(int j=1;j<=m;++j)
 52            {
 53             memset(head,0,sizeof(head));
 54             last=now; now^=1;
 55                cnt[now]=0;
 56             for(int k=1;k<=cnt[last];++k)
 57             {
 58                    long long bit=que[last][k],num=val[last][k]+a[i][j];
 59                    long long b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4;
 60                    if(!b1&&!b2)
 61                 {
 62                     insert(bit,num-a[i][j]);
 63                        if(i!=n&&j!=m) insert(bit+inc[j-1]+inc[j]*2,num);
 64                    }
 65                 else if(!b1&&b2)
 66                 {
 67                        if(j!=m) insert(bit,num);
 68                        if(i!=n) insert(bit-inc[j]*b2+inc[j-1]*b2,num);
 69                    }
 70                 else if(b1&&!b2)
 71                 {
 72                        if(i!=n) insert(bit,num);
 73                        if(j!=m) insert(bit-inc[j-1]*b1+inc[j]*b1,num);
 74                    }
 75                 else if(b1==1&&b2==1)
 76                 {
 77                        int flag=1;
 78                        for(int l=j+1;l<=m;++l)
 79                     {
 80                            if((bit>>(l*2))%4==1) flag++;
 81                            if((bit>>(l*2))%4==2) flag--;
 82                            if(!flag)
 83                         {
 84                                insert(bit-inc[j]-inc[j-1]-inc[l],num);
 85                                break;
 86                            }
 87                        }
 88                    }
 89                 else if(b1==2&&b2==2)
 90                 {
 91                        int flag=1;
 92                        for(int l=j-2;l>=0;--l)
 93                        {
 94                            if((bit>>(l*2))%4==1) flag--;
 95                            if((bit>>(l*2))%4==2) flag++;
 96                            if(!flag)
 97                         {
 98                                insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
 99                                break;
100                            }
101                        }
102                    }
103                 else if(b1==2&&b2==1) insert(bit-inc[j-1]*2-inc[j],num);
104                     else if (num>ans) ans=num;
105                }
106            }
107        }
108 }
109 int main()
110 {
111    init();
112    work();
113    printf("%lld
",ans);
114    return 0;
115 }

View Code of P3190

hdu 1964

题目大意：

每个相邻格子之间有一个墙，走过需要花费一定的代价，现在求经过所有点的闭合回路的最小代价。

题目分析：

通过上一题，我们学会了求最大值，最小值同理。这里的代价不在格点上在插头上，稍微转换下就行了。

代码如下：

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<string>
  6 using namespace std;
  7 const long long hs=29987;
  8 long long n,m,ex,ey,now,last,ans;
  9 long long a[13][13],h[13][13],l[13][13],head[200000],nex[200000],que[2][200000],val[2][200000],cnt[2],inc[13];
 10 void init()
 11 {
 12     memset(a,0,sizeof(a));
 13     memset(h,0,sizeof(h));
 14     memset(l,0,sizeof(l));
 15     memset(head,0,sizeof(head));    
 16     memset(nex,0,sizeof(nex));     
 17     memset(que,0,sizeof(que));
 18     memset(val,0,sizeof(val));
 19     memset(cnt,0,sizeof(cnt));
 20     memset(inc,0,sizeof(inc)); 
 21     string str;
 22     scanf("%lld%lld",&n,&m);
 23     for (int i=1;i<=n;i++)
 24     {
 25         for (int j=1;j<=m;j++)
 26         {
 27             a[i][j]=1;
 28         }
 29     }
 30     ex=n;
 31     ey=m;
 32     getline(cin,str);
 33     getline(cin,str);
 34     ans=0;
 35     for (int i=1;i<=n-1;i++)
 36     {
 37         char ch=getchar();
 38         while (ch!='#') ch=getchar();
 39         for (int j=1;j<=m-1;j++)
 40         {
 41             scanf("%d",&h[i][j]);
 42             ans=ans+abs(h[i][j]);
 43         }
 44         getline(cin,str);
 45         for (int j=1;j<=m;j++)
 46         {
 47             ch=getchar();
 48             while (ch!='#') ch=getchar();
 49             scanf("%d",&l[i][j]);
 50             ans=ans+abs(l[i][j]);
 51         } 
 52         getline(cin,str);
 53     }
 54     char ch=getchar();
 55     while (ch!='#') ch=getchar();
 56     for (int j=1;j<=m-1;j++)
 57     {
 58         scanf("%d",&h[n][j]);
 59         ans=ans+abs(h[n][j]);
 60     }
 61     getline(cin,str);
 62     getline(cin,str); 
 63     inc[0]=1;
 64     for(int i=1;i<=13;i++)
 65     {
 66        inc[i]=inc[i-1]<<2;
 67     }
 68 }
 69 inline void insert(long long bit,long long num)
 70 {
 71    long long u=bit%hs+1;
 72    for(int i=head[u];i;i=nex[i])
 73    {
 74        if(que[now][i]==bit)
 75        {
 76            if (val[now][i]>num) val[now][i]=num;
 77            return;
 78        }
 79    }
 80    nex[++cnt[now]]=head[u];
 81    head[u]=cnt[now];
 82    que[now][cnt[now]]=bit;
 83    val[now][cnt[now]]=num;
 84 }
 85 inline void solve()
 86 {
 87     cnt[now]=1; 
 88     val[now][1]=0; 
 89     que[now][1]=0;
 90     for(int i=1;i<=n;i++)
 91     {
 92         for(int j=1;j<=cnt[now];j++)
 93         {
 94             que[now][j]<<=2;
 95         }
 96            for(int j=1;j<=m;++j)
 97            {
 98             memset(head,0,sizeof(head));
 99             last=now; now^=1;
100                cnt[now]=0;
101             for(int k=1;k<=cnt[last];++k)
102             {
103                 long long bit=que[last][k],num=val[last][k];
104                 long long b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4;
105                    if (b1) num=num+h[i][j-1];
106                    if (b2) num=num+l[i-1][j];
107                    if(!b1&&!b2)
108                 {
109                        if(a[i+1][j]&&a[i][j+1]) insert(bit+inc[j-1]+inc[j]*2,num);
110                    }
111                 else if(!b1&&b2)
112                 {
113                        if(a[i][j+1]) insert(bit,num);
114                        if(a[i+1][j]) insert(bit-inc[j]*b2+inc[j-1]*b2,num);
115                    }
116                 else if(b1&&!b2)
117                 {
118                        if(a[i+1][j]) insert(bit,num);
119                        if(a[i][j+1]) insert(bit-inc[j-1]*b1+inc[j]*b1,num);
120                    }
121                 else if(b1==1&&b2==1)
122                 {
123                        int flag=1;
124                        for(int l=j+1;l<=m;++l)
125                     {
126                            if((bit>>(l*2))%4==1) flag++;
127                            if((bit>>(l*2))%4==2) flag--;
128                            if(!flag)
129                         {
130                                insert(bit-inc[j]-inc[j-1]-inc[l],num);
131                                break;
132                            }
133                        }
134                    }
135                 else if(b1==2&&b2==2)
136                 {
137                        int flag=1;
138                        for(int l=j-2;l>=0;--l)
139                        {
140                            if((bit>>(l*2))%4==1) flag--;
141                            if((bit>>(l*2))%4==2) flag++;
142                            if(!flag)
143                         {
144                                insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
145                                break;
146                            }
147                        }
148                    }
149                 else if(b1==2&&b2==1) insert(bit-inc[j-1]*2-inc[j],num);
150                     else if(i==ex&&j==ey) if (num<ans) ans=num;
151                }
152            }
153        }
154 }
155 int main()
156 {
157     int t;
158     scanf("%d",&t);
159     while (t--)
160     {
161         init();
162         solve();
163         printf("%lld
",ans);        
164     }
165     return 0;
166 }

View Code of HDU1964

poj 1739

题目大意：

有些格点必须走，有些不能走，问从左下角走到右下角多少种路径。

题目分析：

我们可以在最后加两行，第一行只有头尾可走，第二行全部可走，然后就转换为了回路问题。楼教主男人八题之一，不过记得调一下hash参数。1e5会tle，1e4就行了。

代码如下：

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<cstring>
  4 using namespace std;
  5 const long long hs=29987;
  6 long long n,m,ex,ey,now,last,ans;
  7 long long a[13][13],head[300010],nex[300010],que[2][300010],val[2][300010],cnt[2],inc[13];
  8 void init()
  9 {
 10     ans=0;
 11     memset(a,0,sizeof(a));
 12     memset(head,0,sizeof(head));    
 13     memset(nex,0,sizeof(nex));     
 14     memset(que,0,sizeof(que));
 15     memset(val,0,sizeof(val));
 16     memset(cnt,0,sizeof(cnt));
 17     memset(inc,0,sizeof(inc)); 
 18     scanf("%lld%lld",&n,&m);
 19     for (int i=1;i<=n;i++)
 20     {
 21         for (int j=1;j<=m;j++)
 22         {
 23             char ch=getchar();
 24             while (ch!='#'&&ch!='.') ch=getchar();
 25             if (ch!='.') a[i][j]=0;
 26             else 
 27             {
 28                 a[i][j]=1;
 29             }
 30         }
 31     }
 32     string str;
 33     a[n+1][1]=1;
 34     a[n+1][m]=1;
 35     for (int j=2;j<=m-1;j++)
 36     {
 37         a[n+1][j]=0;
 38     }
 39     for (int j=1;j<=m;j++)
 40     {
 41         a[n+2][j]=1;
 42     }
 43     n=n+2;
 44     ex=n;
 45     ey=m;
 46     inc[0]=1;
 47     for(int i=1;i<=13;i++)
 48     {
 49        inc[i]=inc[i-1]<<2;
 50     }
 51 }
 52 inline void insert(long long bit,long long num)
 53 {
 54    long long u=bit%hs+1;
 55    for(int i=head[u];i;i=nex[i])
 56    {
 57        if(que[now][i]==bit)
 58        {
 59            val[now][i]+=num;
 60            return;
 61        }
 62    }
 63    nex[++cnt[now]]=head[u];
 64    head[u]=cnt[now];
 65    que[now][cnt[now]]=bit;
 66    val[now][cnt[now]]=num;
 67 }
 68 inline void solve()
 69 {
 70     cnt[now]=1; 
 71     val[now][1]=1; 
 72     que[now][1]=0;
 73     for(int i=1;i<=n;i++)
 74     {
 75         for(int j=1;j<=cnt[now];j++)
 76         {
 77             que[now][j]<<=2;
 78         }
 79            for(int j=1;j<=m;++j)
 80            {
 81             memset(head,0,sizeof(head));
 82             last=now; now^=1;
 83                cnt[now]=0;
 84             for(int k=1;k<=cnt[last];++k)
 85             {
 86                    long long bit=que[last][k],num=val[last][k];
 87                    long long b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4;
 88                    if(!a[i][j])
 89                    {
 90                    if(!b1&&!b2) insert(bit,num);
 91                    }
 92                    else if(!b1&&!b2)
 93                 {
 94                        if(a[i+1][j]&&a[i][j+1]) insert(bit+inc[j-1]+inc[j]*2,num);
 95                    }
 96                 else if(!b1&&b2)
 97                 {
 98                        if(a[i][j+1]) insert(bit,num);
 99                        if(a[i+1][j]) insert(bit-inc[j]*b2+inc[j-1]*b2,num);
100                    }
101                 else if(b1&&!b2)
102                 {
103                        if(a[i+1][j]) insert(bit,num);
104                        if(a[i][j+1]) insert(bit-inc[j-1]*b1+inc[j]*b1,num);
105                    }
106                 else if(b1==1&&b2==1)
107                 {
108                        int flag=1;
109                        for(int l=j+1;l<=m;++l)
110                     {
111                            if((bit>>(l*2))%4==1) flag++;
112                            if((bit>>(l*2))%4==2) flag--;
113                            if(!flag)
114                         {
115                                insert(bit-inc[j]-inc[j-1]-inc[l],num);
116                                break;
117                            }
118                        }
119                    }
120                 else if(b1==2&&b2==2)
121                 {
122                        int flag=1;
123                        for(int l=j-2;l>=0;--l)
124                        {
125                            if((bit>>(l*2))%4==1) flag--;
126                            if((bit>>(l*2))%4==2) flag++;
127                            if(!flag)
128                         {
129                                insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
130                                break;
131                            }
132                        }
133                    }
134                 else if(b1==2&&b2==1) insert(bit-inc[j-1]*2-inc[j],num);
135                     else if(i==ex&&j==ey) ans+=num;
136                }
137            }
138        }
139 }
140 int main()
141 {
142        while (1)
143        {
144         init();
145         if (n==2&&m==0) break;
146            solve();
147            printf("%lld
",ans);
148        }
149        return 0;
150 }

View Code of POJ1739

hdu 4285

题目大意：

n*m的棋盘，有些格子不能走，有些必须走。问没有回路套回路且总共k条回路方案数。

题目分析：

这个题目调了一会儿哈希，mle了一会儿。最后把nex，head数组，longlong变int，qaq。
题目有两个变化，第一个是k条回路，好处理。压进状态里就行了。另一个是回路套回路，让某个回路合拢时，左侧括号时奇数个，则出现了回路套回路，因为总数为偶数，左侧为奇数则右侧也为奇数。每次合拢只能在一边消去2个，最后一定是回路套回路。这个题目最小表示时限勉强，括号匹配无压力。

代码如下：

  1 /*
  2 bit最高三位用来标记k
  3 (m+1)个位用来标记插头 
  4 */
  5 #include<stdio.h>
  6 #include<iostream>
  7 #include<cstring>
  8 using namespace std;
  9 const long long hs=199987;
 10 const long long mod=1e9+7;
 11 long long n,m,ex,ey,now,last,ans,sk;
 12 int a[15][15],head[800010],nex[800010],que[2][800010],cnt[2],inc[15];
 13 long long val[2][800010];
 14 void init()
 15 {
 16     ans=0;
 17     memset(a,0,sizeof(a));
 18     memset(head,0,sizeof(head));    
 19     memset(nex,0,sizeof(nex));     
 20     memset(que,0,sizeof(que));
 21     memset(val,0,sizeof(val));
 22     memset(cnt,0,sizeof(cnt));
 23     memset(inc,0,sizeof(inc)); 
 24     scanf("%lld%lld%lld",&n,&m,&sk);
 25     if (sk>36) sk=37; 
 26     for (int i=1;i<=n;i++)
 27     {
 28         for (int j=1;j<=m;j++)
 29         {
 30             char ch=getchar();
 31             while (ch!='*'&&ch!='.') ch=getchar();
 32             if (ch!='.') a[i][j]=0;
 33             else 
 34             {
 35                 a[i][j]=1;
 36                 ex=i;
 37                 ey=j;
 38             }
 39         }
 40     }
 41     inc[0]=1;
 42     for(int i=1;i<=14;i++)
 43     {
 44        inc[i]=inc[i-1]<<2;
 45     }
 46 }
 47 inline void insert(long long bit,long long num)
 48 {
 49    long long u=bit%hs+1;
 50    for(int i=head[u];i;i=nex[i])
 51    {
 52        if(que[now][i]==bit)
 53        {
 54            val[now][i]=(val[now][i]+num)%mod;
 55            return;
 56        }
 57    }
 58    nex[++cnt[now]]=head[u];
 59    head[u]=cnt[now];
 60    que[now][cnt[now]]=bit;
 61    val[now][cnt[now]]=num;
 62 }
 63 inline void solve()
 64 {
 65     cnt[now]=1; 
 66     val[now][1]=1; 
 67     que[now][1]=0;
 68     for(int i=1;i<=n;i++)
 69     {
 70         for(int j=1;j<=cnt[now];j++)
 71         {
 72             long long t=que[now][j]/inc[m+1];
 73             que[now][j]=((que[now][j]-t*inc[m+1])<<2)+t*inc[m+1];
 74         }
 75            for(int j=1;j<=m;++j)
 76            {
 77             memset(head,0,sizeof(head));
 78             last=now; now^=1;
 79                cnt[now]=0;
 80 //          cout<<i<<" "<<j<<"   ："<<endl;
 81 //            cout<<"--------------"<<endl; 
 82             for(int k=1;k<=cnt[last];++k)
 83             {
 84                    long long bit=que[last][k],num=val[last][k];
 85                    long long b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4,t=bit/inc[m+1];
 86 //                   cout<<bit<<endl;
 87 //                   cout<<b1<<" "<<b2<<" "<<t<<endl; 
 88 //                   cout<<"-----------------"<<endl;
 89                    if(!a[i][j])
 90                    {
 91                    if(!b1&&!b2) insert(bit,num);
 92                    }
 93                    else if(!b1&&!b2)
 94                 {
 95                        if(a[i+1][j]&&a[i][j+1]) insert(bit+inc[j-1]+inc[j]*2,num);
 96                    }
 97                 else if(!b1&&b2)
 98                 {
 99                        if(a[i][j+1]) insert(bit,num);
100                        if(a[i+1][j]) insert(bit-inc[j]*b2+inc[j-1]*b2,num);
101                    }
102                 else if(b1&&!b2)
103                 {
104                        if(a[i+1][j]) insert(bit,num);
105                        if(a[i][j+1]) insert(bit-inc[j-1]*b1+inc[j]*b1,num);
106                    }
107                 else if(b1==1&&b2==1)
108                 {
109                        int flag=1;
110                        for(int l=j+1;l<=m;++l)
111                     {
112                            if((bit>>(l*2))%4==1) flag++;
113                            if((bit>>(l*2))%4==2) flag--;
114                            if(!flag)
115                         {
116                                insert(bit-inc[j]-inc[j-1]-inc[l],num);
117                                break;
118                            }
119                        }
120                    }
121                 else if(b1==2&&b2==2)
122                 {
123                        int flag=1;
124                        for(int l=j-2;l>=0;--l)
125                        {
126                            if((bit>>(l*2))%4==1) flag--;
127                            if((bit>>(l*2))%4==2) flag++;
128                            if(!flag)
129                         {
130                                insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
131                                break;
132                            }
133                        }
134                    }
135                 else if(b1==2&&b2==1) insert(bit-inc[j-1]*2-inc[j],num);
136                 else
137                 {
138                     int flag=0;
139                     for (int jj=0;jj<=j-2;jj++)
140                     {
141                         if ((bit>>((jj)*2))%4!=0) flag=1-flag;
142                     }
143                     if (flag) continue;
144                     if (t==sk-1&&i==ex&&j==ey) ans=(ans+num)%mod;
145                         else insert(bit-inc[j-1]-inc[j]*2+inc[m+1],num);
146                 }
147                }
148            }
149        }
150 }
151 int main()
152 {
153     int t;
154     scanf("%d",&t); 
155     while(t--)
156     {
157            init();
158            solve();
159            printf("%lld
",ans);
160        }
161        return 0;
162 }

View Code of HDU4285

hdu 6875

题目大意：
一个n*n的棋盘，每个格子有个权值，让你染黑一些两两不相邻格子使得黑格权值和最大且剩下的格子可以组成一个回路。
题目分析：
黑色权值最大就是白色回路权值和最小。
至于染色问题，意外的好处理，因为黑色格子没有插头，其实就是原来的0状态要分成黑白两种，正好原来只有左右括号（1，2）和白0，用的4进制，剩下来的3分给黑0。转移稍微多加了几个分类讨论。需要注意的是，因为黑色不连续，终止格点即最后白格可以是最后一个，或者倒数第二个。
另：这题30组，不能无脑memset，否则tle。要用mark数组标记哈希表来清零用过的。
代码如下：

  1 /*
  2 bit 0 无插头为白格 
  3 bit 1 左括号 
  4 bit 2 右括号 
  5 bit 3 黑格 
  6 */
  7 #include<stdio.h>
  8 #include<iostream>
  9 #include<cstring>
 10 using namespace std;
 11 const long long hs=299987;
 12 long long n,m,ex,ey,now,last,ans,sum,s;
 13 long long a[13][13],b[13][13],head[300010],nex[300010],mark[300010];
 14 long long que[2][300010],val[2][300010],cnt[2],inc[14];
 15 void init()
 16 {
 17     memset(a,0,sizeof(a));
 18     memset(b,0,sizeof(b));
 19     sum=0;
 20     ans=1e9+7;
 21     scanf("%lld",&n);
 22     for (int i=1;i<=n;i++)
 23     {
 24         for (int j=1;j<=n;j++)
 25         {
 26             scanf("%lld",&b[i][j]); 
 27             sum=sum+b[i][j];
 28             a[i][j]=1;
 29         }
 30     }
 31     inc[0]=1;
 32     for(int i=1;i<=13;i++)
 33     {
 34        inc[i]=inc[i-1]<<2;
 35     }
 36 }
 37 inline void insert(long long bit,long long num)
 38 {
 39    long long u=bit%hs+1;
 40    if (mark[u]!=s) 
 41    {
 42            head[u]=0;
 43            mark[u]=s;
 44    }
 45    for(int i=head[u];i;i=nex[i])
 46    {
 47        if(que[now][i]==bit)
 48        {
 49            if (val[now][i]>num) val[now][i]=num;
 50            return;
 51        }
 52    }
 53    nex[++cnt[now]]=head[u];
 54    head[u]=cnt[now];
 55    que[now][cnt[now]]=bit;
 56    val[now][cnt[now]]=num;
 57 }
 58 inline void solve()
 59 {
 60     cnt[now]=1; 
 61     val[now][1]=0; 
 62     que[now][1]=0;
 63     for(int i=1;i<=n;i++)
 64     {
 65         for(int j=1;j<=cnt[now];j++)
 66         {
 67             que[now][j]<<=2;
 68         }
 69            for(int j=1;j<=n;++j)
 70            {
 71             s++;
 72             last=now; now^=1;
 73                cnt[now]=0;
 74             for(int k=1;k<=cnt[last];++k)
 75             {
 76                    long long bit=que[last][k],num=val[last][k]+b[i][j];
 77                    long long b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4;
 78                 if (b1==3&&b2==3)
 79                 {
 80                     if(a[i+1][j]&&a[i][j+1]) insert(bit-inc[j-1]*2-inc[j],num);
 81                 }
 82                 else if (b1==3&&b2==0)
 83                 {
 84                     if(a[i+1][j]&&a[i][j+1]) insert(bit-inc[j-1]*3+inc[j-1]+inc[j]*2,num);
 85                 }
 86                 else if (b1==3)
 87                 {
 88                     if(a[i][j+1]) insert(bit-inc[j-1]*3,num);
 89                        if(a[i+1][j]) insert(bit-inc[j-1]*3-inc[j]*b2+inc[j-1]*b2,num);
 90                 }
 91                 else if (b2==3&&b1==0)
 92                 {
 93                     if(a[i+1][j]&&a[i][j+1]) insert(bit-inc[j]*3+inc[j-1]+inc[j]*2,num);
 94                 }
 95                 else if (b2==3)
 96                 {
 97                     if(a[i+1][j]) insert(bit-inc[j]*3,num);
 98                        if(a[i][j+1]) insert(bit-inc[j]*3-inc[j-1]*b1+inc[j]*b1,num);
 99                 }    
100                 else if(!b1&&!b2)
101                 {
102                     //if (i==n&&j==n&&num-b[i][j]<ans) ans=num-b[i][j];
103                     long long newbit=bit;
104                     if (a[i][j+1]) newbit=newbit+inc[j]*3;
105                     if (a[i+1][j]) newbit=newbit+inc[j-1]*3;
106                     insert(newbit,num-b[i][j]);
107                        if(a[i+1][j]&&a[i][j+1]) insert(bit+inc[j-1]+inc[j]*2,num);
108                    }
109                 else if(!b1&&b2)
110                 {
111                        if(a[i][j+1]) insert(bit,num);
112                        if(a[i+1][j]) insert(bit-inc[j]*b2+inc[j-1]*b2,num);
113                    }
114                 else if(b1&&!b2)
115                 {
116                        if(a[i+1][j]) insert(bit,num);
117                        if(a[i][j+1]) insert(bit-inc[j-1]*b1+inc[j]*b1,num);
118                    }
119                 else if(b1==1&&b2==1)
120                 {
121                        int flag=1;
122                        for(int l=j+1;l<=n;++l)
123                     {
124                            if((bit>>(l*2))%4==1) flag++;
125                            if((bit>>(l*2))%4==2) flag--;
126                            if(!flag)
127                         {
128                                insert(bit-inc[j]-inc[j-1]-inc[l],num);
129                                break;
130                            }
131                        }
132                    }
133                 else if(b1==2&&b2==2)
134                 {
135                        int flag=1;
136                        for(int l=j-2;l>=0;--l)
137                        {
138                            if((bit>>(l*2))%4==1) flag--;
139                            if((bit>>(l*2))%4==2) flag++;
140                            if(!flag)
141                         {
142                                insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
143                                break;
144                            }
145                        }
146                    }
147                 else if(b1==2&&b2==1) insert(bit-inc[j-1]*2-inc[j],num);
148                 else if (i==n&&j==n) 
149                 {
150                     if (num<ans) ans=num;
151                 }
152                 else if (i==n&&j==n-1)
153                 {
154                     long long b3=(bit>>(j*2+2))%4;
155                     if (b3==0&&num<ans) ans=num;
156                 }
157                }
158            }
159        }
160 }
161 int main()
162 {
163     int t;
164     scanf("%d",&t);
165     while (t--)
166     { 
167            init();
168            solve();
169            printf("%lld
",sum-ans);
170        }
171        return 0;
172 }

View Code of HDU6875