题意：给一个n*m的矩阵，为1时代表空格子，为0时代表障碍格子，问如果不经过障碍格子，可以画一至多个圆的话，有多少种方案？（n<12，m<12）
思路：
这题不需要用到最小表示法以及括号表示法。
以一个非障碍格子为单位进行DP转移，所以可以用滚动数组。只需要保存m+1个插头的状态，其中有一个是右插头，其他都是下插头，若有插头的存在，该位为1，否则为0，初始时都是0。
需要考虑的是，（1）如果两个边缘都是插头，那么必须接上它们；（2）如果仅有一边是插头，则延续插头，可以有两个延续的方向（下和右）；（3）如果都没有插头，那么必须另开两个新插头（新连通分量）。
如下图，记录的状态是：101111。由于是按行来保存状态的，第一个格子需要特殊考虑，将所有状态左移一位，最后的一位就是右方向的边缘。假设上行都有下插头，那么此行初始时是011111，可以看到最左边的是0，表示无右插头，注意：我是按照111110保存的，即最低位是最左边。
初始格子dp[0][0]=1，而答案就是dp[cur][0]了，肯定是无插头存在的状态了，所有的圆圈都是完整的。
#include <bits/stdc++.h>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=;
int g[N][N], cur;
LL dp[N][<<N]; void clear()
{
cur^=;
memset(dp[cur], , sizeof(dp[cur]));
} LL cal(int n,int m)
{
dp[][]=; //开始时没有任何插头
for(int i=; i<n; i++) //枚举格子
{
clear();
for(int k=; k<(<<m); k++) dp[cur][k<<]+=dp[cur^][k]; //最高位自动会被忽略
for(int j=; j<m; j++)
{
int r=(<<j), d=(<<(j+)); //r和d 相当于 右和下
clear();
for(int k=; k<(<<(m+)); k++) //枚举状态
{
if(g[i][j]) //空格
{
if( (k&r) && (k&d) ) //两边都有插头:连起来，变无插头
dp[cur][k^r^d]+=dp[cur^][k];
else if( k&r || k&d ) //其中一边有插头：可转两个方向
{
dp[cur][k]+=dp[cur^][k];
dp[cur][k^r^d]+=dp[cur^][k];
}
else //无插头：另开两个新插头
dp[cur][k|r|d]=dp[cur^][k];
}
else //障碍格子
{
if( !(k&r) && !(k&d) )
dp[cur][k]=dp[cur^][k];
}
}
}
}
return dp[cur][];
} int main()
{
//freopen("input.txt", "r", stdin);
int n, m, t, Case=;
cin>>t;
while(t--)
{
scanf("%d%d",&n,&m);
memset(g, , sizeof(g));
memset(dp, , sizeof(dp));
for(int i=; i<n; i++)
for(int j=; j<m; j++)
scanf("%d",&g[i][j]);
printf("Case %d: There are %lld ways to eat the trees.\n", ++Case, cal(n,m));
}
return ;
}
AC代码
最小表示法实现：
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=;
int g[N][N], n, m, cur, code[N];
struct Hash_Map
{
static const int mod=;
static const int NN=;
int head[mod]; //桶指针
int next[NN]; //记录链的信息
LL status[NN]; //状态
LL value[NN]; //状态对应的DP值。
int size; void clear()
{
memset(head, -, sizeof(head));
size = ;
} void insert(LL st, LL val)
{
int h = st%mod;
for(int i=head[h]; i!=-; i=next[i])
{
if(status[i] == st)
{
value[i] += val;
return ;
}
}
status[size]= st;
value[size] = val;
next[size] = head[h] ;
head[h] = size++;
}
}hashmap[]; void decode(LL s)
{
for(int i=; i<=m; i++)
{
code[i]=s&;
s>>=;
}
}
int cnt[N];
LL encode()
{
LL s=;
memset(cnt, -, sizeof(cnt));
cnt[]=;
for(int i=m,up=; i>=; i--)
{
if(cnt[code[i]]==-) cnt[code[i]]=++up;
code[i]=cnt[code[i]];
s<<=;
s|=code[i];
}
return s;
} void DP(int i,int j)
{
for(int k=; k<hashmap[cur^].size; k++)
{
decode(hashmap[cur^].status[k]);
LL v=hashmap[cur^].value[k]; int R=code[j], D=code[j+]; if(g[i][j]==)
{
if(R==&&D==) hashmap[cur].insert(encode(),v);
continue;
} if(R&&D)
{
code[j]=code[j+]=;
if(R==D) hashmap[cur].insert(encode(),v);
else
{
for(int r=; r<=m; r++)
if(code[r]==R) code[r]=D;
hashmap[cur].insert(encode(), v);
}
}
else if(R||D)
{
R+=D;
if(i+<n)
{
code[j]=R;
code[j+]=;
hashmap[cur].insert(encode(), v);
}
if(j+<m)
{
code[j]=;
code[j+]=R;
hashmap[cur].insert(encode(), v);
}
}
else
{
code[j]=;
code[j+]=;
if(i+<n && j+<m) hashmap[cur].insert(encode(), v);
}
}
} void cal()
{
cur=;
hashmap[cur].clear();
hashmap[cur].insert(,);
for(int i=; i<n; i++)
{
for(int j=; j<hashmap[cur].size; j++) hashmap[cur].status[j]<<=;
for(int j=; j<m; j++)
{
hashmap[cur^=].clear();
DP(i,j);
//cout<<hashmap[cur].size<<endl;
}
}
} LL print()
{
for(int i=; i<hashmap[cur].size; i++)
if(hashmap[cur].status[i]==)
return hashmap[cur].value[i];
return ;
} int main()
{
//freopen("input.txt", "r", stdin);
int t, Case=;
cin>>t;
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=; i<n; i++)
{
for(int j=; j<m; j++)
{
scanf("%d",&g[i][j]);
}
}
cal();
printf("Case %d: There are %lld ways to eat the trees.\n", ++Case, print());
}
}
AC代码