先%mmh前辈。
这个没问题吧。
压力不大，也做不了什么难事，所以可以写板子的问题。
我们用哈希图代替了哈希表。一、P5056 【模板】插头dp：
主题背景
ural 1519
活跃跳糖《基于连通性状态压缩的动态规划问题》例题
主题说明
露出n*m的网格，有些网格不能铺线，其他网格必须铺，形成闭合回路。 有几种铺法？
输入格式
第一行，n，m(2=n，m=12 ) )。
从第2行至第n 1行，每行必须铺有字符串(m个字符)、(*“表不能划线，)表
输出格式
输出表示方案总数的整数
输入输出样本
输入#1复印
4 4
*…
.
.
.
输出#1复制
2
输入#2复制
4 4
.
.
.
.
输出#2复制
6
# include iostream # include cstdio # include algorithm # include cstring # include cmath # include string # include queue # include me 常数上限=2000 100； 常数int mod=4； char str[maxn][maxn]； int pm[maxn][maxn]，n，m，ex，ey； int b[maxn]，bm[maxn]； int cnt[2]，sta[2][maxx]，k=0； unordered_mapint，lldp[2]； ll ans=0； voidinit(void ) {for ) intI=0； i=13； I ) b(I )=) I1 )； for(intI=0； i=13； I ) BM(I )=(1b ) I )； }voidin(intnowsta，ll sum ) if ) DP[k].find ) nowsta )==dp[k].end ) { sta[k][ cnt[k]]=nowsta； dp[k][nowsta]=sum； } else dp[k][nowsta]=sum； }voidDP(void ) { cnt[k]=1； dp[k][0]=1； sta[k][1]=0； for(intI=1； i=n； I ) for(intj=1； j=m； j () { int p=k； k^=1； dp[k].clear (； cnt[k]=0； for(intcm=1； 广告cm=cnt[p]； 广告({ intnowsta=sta [ p ] [ cm ]； ll sum=dp[p][nowsta]； //前一行移动到下一行的第一格时，没有右插头if (j==1) nowsta=2； intr=(nowstab[j-1] ) %mod； intd=(nowstab[j] ) %mod； if (！ pm[I][j](if(r==0d==0) in ) nowsta，sum )； }elseif(r==0d==0) if ) pm[I1][j]pm[I][j1] ) in ) nowstaBM[j-1]2*BM[j]，sum )； }elseif(r==0d！=0) if(pm[I][j1] ) in ) nowsta，sum )； if(pm[I1][j] ) in ) nowsta-d*BM[j]d*BM[j-1]，sum )； }
else if(r!=0&&d==0) { if(pm[i+1][j]) in(nowsta,sum); if(pm[i][j+1]) in(nowsta-r*bm[j-1]+r*bm[j],sum); } else if(r==1&&d==1) { int cc=1; for(int km=j+1;km<=m;km++) { if((nowsta>>b[km])%4==1) cc++; else if((nowsta>>b[km])%4==2) cc--; if(cc==0) { in(nowsta-bm[km]-bm[j]-bm[j-1],sum); break; } } } else if(r==2&&d==2) { int cc=1; for(int km=j-2;km>=0;km--) { if((nowsta>>b[km])%4==1) cc--; else if((nowsta>>b[km])%4==2) cc++; if(cc==0) { in(nowsta+bm[km]-2*bm[j]-2*bm[j-1],sum); break; } } } else if(r==2&&d==1) in(nowsta-2*bm[j-1]-bm[j],sum); else if(r==1&&d==2) if(ex==i&&ey==j) ans+=sum; } } }}int main(void){ init(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",str[i]+1); memset(pm,0,sizeof(pm)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(str[i][j]=='.') pm[i][j]=1,ex=i,ey=j; } } DP(); printf("%lldn",ans); return 0;}二、P5074 Eat the Trees：
题目背景
HDU1693：Eat the Trees
题目描述
给出n*m的方格，有些格子不能铺线，其它格子必须铺，可以形成多个闭合回路。问有多少种铺法？
输入格式
每个测试点多组数据
第一行一个正整数T，表示有T组数据
每组数据：
第1行，n,m(2<=n,m<=12)
从第2行到第n+1行，每行m个数字（1 or 0），1表铺线，0表不铺线
输出格式
每组数据输出一个整数（表方案数）
输入输出样例
输入 #1 复制
2
6 3
1 1 1
1 0 1
1 1 1
1 1 1
1 0 1
1 1 1
2 4
1 1 1 1
1 1 1 1
输出 #1 复制
3
2
因为本题允许有多个回路，所以不需要括号匹配。不再需要分析是左括号还是右括号。
状态：有插头设为1，无插头设为0。
状态转移与上题差不多，只是本题没有了左右括号的限制，可以随便接插头。