讲解
https://www.luogu.com.cn/problemnew/solution/P5056
https://blog.csdn.net/litble/article/details/79369147
https://blog.csdn.net/zhangjianjunab/article/details/80987531
例1、题目大意:一个网格图中有若干障碍格子，求其他格子的哈密尔顿回路总数
只能有一个回路，有多少种可能
//我觉得这个写法比较好理解
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int mod=200000;//hash表大小，因为hash表有压缩功能，所以一般100万就够了
int map[50][50]={0};
int n,m,ex=-1,ey=-1; //最后一个非障碍格子的坐标
char ss[210];
LL ans=0;
int now,php;
struct node{
int hash[mod]; //压缩状态
int key[mod]; //记录原本的数值
int size; // 记录存了多少次数
LL num[mod]; // 记录当前数值代表了多少状态
void mem(){
memset(hash,-1,sizeof(hash));
size=0; //初始化函数
}
void add(int S,int sum){
int s=S%mod;
while(hash[s]!=-1&&key[hash[s]]!=S){
s++;
s%=mod;
}
//判断重复，保证下一次同样一个数也可以到达这个hash值
if(hash[s]==-1){
hash[s]=++size; //压缩状态
key[size]=S; //存储原本的数值
num[size]=sum; //代表了多少状态
} //新建一个hash格
else num[hash[s]]+=sum; //有的话直接加
}
}dp[2]; //滚动数组
int set(int s,int p){
return (s>>((p-1)*2))&3; //取出第p个位置的数
}
void change(int &s,int p,int v){
s^=set(s,p)<<((p-1)*2);
s^=(v&3)<<((p-1)*2); //改变第p位上的数位v
}
void wrok(){
LL sum=0;
now=0,php=1;
dp[now].mem();
dp[now].add(0,1); //初始化滚动型DP数组
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
swap(now,php); //使用滚动数组
dp[now].mem();
for(int k=1;k<=dp[php].size;k++){
int s=dp[php].key[k];
sum=dp[php].num[k];
int q=set(s,j); //右插头
int p=set(s,j+1); //下插头
if(map[i][j]==0){ //障碍格子 ，不能有插头
if(p==0&&q==0) dp[now].add(s,sum);
continue;
}
if(q==0&&p==0){ //|一 没人指我，只好自己建一个插头
if(map[i+1][j]==1&&map[i][j+1]==1){ //判断是不是障碍格子
change(s,j,1); //
change(s,j+1,2);//从这个格子建两个插头
dp[now].add(s,sum);
}
}
else if(q>0&&p==0){ //两种方式
if(map[i+1][j]==1) dp[now].add(s,sum); //不会改变
if(map[i][j+1]==1){ //把插头指向右边，继承下去
change(s,j,0);
change(s,j+1,q); //相当于交换这两列
dp[now].add(s,sum);
}
}
else if(q==0&&p>0){ //跟上面一样，两种方式
if(map[i][j+1]==1) dp[now].add(s,sum);
if(map[i+1][j]==1){
change(s,j,p);
change(s,j+1,0);
dp[now].add(s,sum);
}
}
else if(q==1&&p==1){
int find=1; //算上p为1！很重要。
for(int tt=j+2;tt<=m;tt++){ //找到与p相对的右插头并修改为这一大块插头的左插头
int vs=set(s,tt);
if(vs==1) find++;
else if(vs==2) find--;////为什么可以？因为中间罩住的插头不会出去这个大插头的范围，所以只有碰到与p成对的插头才会清零
if(find==0){
change(s,j,0);
change(s,j+1,0);
change(s,tt,1);
dp[now].add(s,sum);
break;
}
}
}
else if(q==2&&p==2){
int find=1;
for(int tt=j-1;tt>=1;tt--){ ///找到与q相对的左插头并修改为这一大块插头的右插头
int vs=set(s,tt);
if(vs==2) find++;
else if(vs==1) find--;
if(find==0){
change(s,j,0);
change(s,j+1,0);
change(s,tt,2);
dp[now].add(s,sum);
break;
}
}
}
else if(q==2&&p==1){ //这样配对的插头刚好是我们想要的
change(s,j,0);
change(s,j+1,0); //直接抵消清零就可以了
dp[now].add(s,sum);
}
else if(q==1&&p==2){
if(ex==i&&ey==j) ans+=sum;//得到答案
}
}
}
for(int j=1;j<=dp[now].size;j++) dp[now].key[j]<<=2;
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",ss+1);
for(int j=1;j<=m;j++){
if(ss[j]=='.'){
map[i][j]=1;
ex=i;
ey=j;
}
}
}
if(ex==-1) {
printf("0
");
return 0;
}
wrok();
printf("%lld
",ans);
return 0;
}
例2、有多个回路，有多少种可能
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m;
int bin[15],mp[15][15];
LL f[12][12][(1<<12)];
int t;
int l=1;
//这道题的回路数目不限，所以只需要记录有没有插头的状态，
int main(){
scanf("%d",&t);
bin[0]=1; //预处理
for(int i=1;i<=12;i++) bin[i]=bin[i-1]<<1;
while(t--){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]);
}
memset(f,0,sizeof(f)); //每次都清零
f[0][m][0]=1;
int lim=bin[m+1]-1; //状态数
for(int i=1;i<=n;i++){
for(int zt=0;zt<=lim;zt++) f[i][0][zt<<1]=f[i-1][m][zt]; ///!!!!
for(int j=1;j<=m;j++)
for(int zt=0;zt<=lim;zt++){
int b1=zt&bin[j-1];
int b2=zt&bin[j];
LL num=f[i][j-1][zt];
if(!mp[i][j]){
if(!b1&&!b2) f[i][j][zt]+=num;
continue;
}
if(!b1&&!b2){
if(mp[i][j+1]&&mp[i+1][j]) f[i][j][zt+bin[j-1]+bin[j]]+=num;
}
else if(!b1&&b2){
if(mp[i][j+1]) f[i][j][zt]+=num;
if(mp[i+1][j]) f[i][j][zt-bin[j]+bin[j-1]]+=num;
}
else if(b1&&!b2){
if(mp[i][j+1]) f[i][j][zt-bin[j-1]+bin[j]]+=num;
if(mp[i+1][j]) f[i][j][zt]+=num;
}
else f[i][j][zt-bin[j-1]-bin[j]]+=num;
}
}
printf("Case %d: There are %lld ways to eat the trees.
",l++,f[n][m][0]);
}
return 0;
}