首页 > 代码库 > 【插头DP】BZOJ1814-Formula

【插头DP】BZOJ1814-Formula

【题目大意】

给出一个m*n的矩阵里面有一些格子为障碍物,求经过所有非障碍格子的哈密顿回路个数。

【思路】

最典型的插头DP。分为三种情况:

(1)当前格子既没有上插头也没有左插头。

如果下边和右边都没有障碍,新建连同分量。

(2)如果只有左插头或者右插头。

延伸或者拐弯,当然也要判断有没有障碍。

(3)上插头和左插头都没有。

1. 如果两个插头不连通(编号不一样),那么将两个插头所处的连通分量合并,标记相同的连通块标号,O(n)扫描保证最小表示;
2. 如果已经连通,相当于出现了一个回路,这种情况只能出现在最后一个非障碍格子。

由于状态非常多,用hash表存储状态。

decode和encode注意一下,这里不赘述了。

【错误点】

注意一下ch要开得够大,具体见代码。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long ll; 7 const int MAXN=11; 8 ll dp[2][1<<MAXN]; 9 10 void solve(int m,int n)11 {12     if (m<n) swap(m,n);13     int cur=0;14     memset(dp,0,sizeof(dp));15     dp[cur][(1<<n)-1]=1;16     for (int i=1;i<=m;i++)17         for (int j=1;j<=n;j++)18         {19             cur^=1;20             /*cur要放在第二重循环后面,一开始写在了三重循环里面*/ 21             memset(dp[cur],0,sizeof(dp[cur]));22             /*不要忘了要清空当前状态*/23             for (int k=0;k<=(1<<n)-1;k++)24             {25                 //上放26                 if (i!=1 && !(k&(1<<(n-1))))27                 {28                     int now=(((k<<1)|1)&((1<<n)-1));29                     dp[cur][now]+=dp[1-cur][k];30                 } 31                 //不放32                 if (k&(1<<(n-1)))33                 {34                     int now=((k<<1)&((1<<n)-1));35                     dp[cur][now]+=dp[1-cur][k];36                 }37                 //左放 38                 if (j!=1 && (k&(1<<(n-1))) && !(k&1))39                 {40                     int now=(((k<<1)|3)&((1<<n)-1));41                     dp[cur][now]+=dp[1-cur][k];42                 } 43             }44         }45     cout<<dp[cur][(1<<n)-1]<<endl;46 }47 48 int main()49 {50     int m,n;51     while (scanf("%d%d",&m,&n))52     {53         if (m==n && n==0) break;54         solve(m,n);55     }56     return 0;57 }

 

【插头DP】BZOJ1814-Formula