题意: 给出一个n*m大小的01矩阵,在其中画线连成封闭图形,其中对每一个值为1的方格,线要恰好穿入穿出共两次,对每一个值为0的方格,所画线不能经过。
参考资料: 《基于连通性状态压缩的动态规划问题》 ——陈丹琦 2008年国家集训队论文
递推过程中,按照 遍历行->遍历行上每一格->遍历 “轮廓线跨过该格时所有可能的状态变化” 的顺序
这样复杂度是 O(n*m*2m+1) (m+1是因为轮廓线上有m个单元是与列数对应的,另有一单独的竖线单元)
问题关键点在于解决 “轮廓线跨过该格时所有可能的状态变化”
首先是由第i行到第i+1行的递推关系。显然,第i+1行上,轮廓线未跨过任何方格,与在第i行,轮廓线跨过了所有方格,这两者轮廓线的形态是相同的,不过,前者的状态state1应表示为后者的状态state2<<1,在代码中,计数关系通过 for(int k=0;k<M;k++) dp[i][0][k<<1]=dp[i-1][m][k]; 来实现。
然后是在同一行上跨过某一格时的递推关系。不考虑方格值为0,这道题里面共有四种情况,对于具体某一格而言,即 00->11,01->10,10->01,11->00。对于方格值为0的情况,显然只能是00->00。
后继状态总计数=sigma合法的前驱状态。
具体可以借助代码来理解
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; const int maxn=; int n,m;
int mp[maxn][maxn];
LL dp[maxn][maxn][<<maxn]; LL solve()
{
int M=<<(m+); //轮廓线上状态总数
dp[][m][]=;
for(int i=;i<=n;i++) //遍历行
{
for(int k=;k<M;k++)
dp[i][][k<<]=dp[i-][m][k];
for(int j=;j<=m;j++) //j用来指示轮廓线中小竖线的位置
{
int state1=(<<j),state2=(<<(j-));
for(int k=;k<M;k++)
{
if(mp[i][j])
{
if((k&state1)==&&(k&state2)==)
dp[i][j][k]=dp[i][j-][k+state1+state2];
else if((k&state1)!=&&(k&state2)!=)
dp[i][j][k]=dp[i][j-][k-state1-state2];
else if((k&state1)==&&(k&state2)!=)
{
dp[i][j][k]+=dp[i][j-][k-state2+state1];
dp[i][j][k]+=dp[i][j-][k];
}
else
{
dp[i][j][k]+=dp[i][j-][k-state1+state2];
dp[i][j][k]+=dp[i][j-][k];
}
}
else
if((k&state1)==&&(k&state2)==)
dp[i][j][k]=dp[i][j-][k];
}
}
}
return dp[n][m][];
} int main()
{
int T,kase=;
scanf("%d",&T);
while(T--)
{
memset(dp,,sizeof(dp));
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&mp[i][j]);
printf("Case %d: There are %lld ways to eat the trees.\n",++kase,solve());
}
}