插头dp/轮廓线dp

先%mmh学长。
这个东西还好吧。。。。
也算是个状压，难的也不会，就会写个板子题。
用哈希map代替了哈希表。
一、P5056 【模板】插头dp：
题目背景
ural 1519

陈丹琦《基于连通性状态压缩的动态规划问题》中的例题

题目描述
给出n*m的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？

输入格式
第1行，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<map>
#include<unordered_map>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=20;
const int maxx=2000100;
const 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_map<int,ll>dp[2];
ll ans=0;

void init(void)
{
    for(int i=0;i<=13;i++)
        b[i]=(i<<1);
    for(int i=0;i<=13;i++)
        bm[i]=(1<<b[i]);
}

void in(int nowsta,ll sum)
{
    if(dp[k].find(nowsta)==dp[k].end())
    {
        sta[k][++cnt[k]]=nowsta;
        dp[k][nowsta]=sum;
    }
    else dp[k][nowsta]+=sum;
}

void DP(void)
{
    cnt[k]=1;
    dp[k][0]=1;
    sta[k][1]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int p=k;
            k^=1;
            dp[k].clear();
            cnt[k]=0;
            for(int cm=1;cm<=cnt[p];cm++)
            {
                int nowsta=sta[p][cm];
                ll sum=dp[p][nowsta];
                //上一行向下一行第一格转移时，没有右插头
                if(j==1) nowsta<<=2;
                int r=(nowsta>>b[j-1])%mod;
                int d=(nowsta>>b[j])%mod;

                if(!pm[i][j])
                {
                    if(r==0&&d==0) in(nowsta,sum);
                }
                else if(r==0&&d==0)
                {
                    if(pm[i+1][j]&&pm[i][j+1])
                        in(nowsta+bm[j-1]+2*bm[j],sum);
                }
                else if(r==0&&d!=0)
                {
                    if(pm[i][j+1]) in(nowsta,sum);
                    if(pm[i+1][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("%lld\n",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。
状态转移与上题差不多，只是本题没有了左右括号的限制，可以随便接插头。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<map>
#include<unordered_map>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=15;
int pm[maxn][maxn],n,m,cnt;
ll dp[maxn][maxn][1<<maxn];
int bm[maxn];

void DP(void)
{
    memset(dp,0,sizeof(dp));
    dp[0][m][0]=1;

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=cnt;j++)
            dp[i][0][j]=dp[i-1][m][j];

        for(int j=1;j<=m;j++)
        {
            for(int cm=0;cm<=cnt;cm++)
            {
                int nowsta=cm;
                ll sum=dp[i][j-1][nowsta];
                //上一行向下一行第一格转移时，没有右插头
                if(j==1) nowsta<<=1;
                int r=(nowsta>>(j-1))&1;
                int d=(nowsta>>j)&1;

                if(!pm[i][j])
                {
                    if(r==0&&d==0) dp[i][j][nowsta]+=sum;
                }
                else if(r==0&&d==0)
                {
                    if(pm[i+1][j]&&pm[i][j+1])
                        dp[i][j][nowsta+bm[j-1]+bm[j]]+=sum;
                }
                else if(r==0&&d!=0)
                {
                    if(pm[i][j+1]) dp[i][j][nowsta]+=sum;
                    if(pm[i+1][j]) dp[i][j][nowsta-bm[j]+bm[j-1]]+=sum;
                }
                else if(r!=0&&d==0)
                {
                    if(pm[i+1][j]) dp[i][j][nowsta]+=sum;
                    if(pm[i][j+1]) dp[i][j][nowsta-bm[j-1]+bm[j]]+=sum;
                }
                //允许有多个回路，其他情况直接接起来就好啦。
                else dp[i][j][nowsta-bm[j-1]-bm[j]]+=sum;
            }
        }
    }
    printf("%lld\n",dp[n][m][0]);
}

int main(void)
{
    for(int i=0;i<=13;i++)
        bm[i]=(1<<i);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        cnt=(1<<(m+1))-1;
        memset(pm,0,sizeof(pm));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                scanf("%d",&pm[i][j]);
        }
        DP();
    }

    return 0;
}