棋盘模型

注意

给定一个m*n的棋盘,和一些限制条件,问(最优)方案数

  • 每一行的状态用01串表示(位 or bitset)
  • 注意隐含条件: m,n<=80,m*n<=80 可知9*9>80 , max(min(m,n)) = 8
  • 可以提前处理出状态:如不能相互攻击,则可以用dfs处理出这一行可行状态;或者通过枚举,确定两(多)行的状态
  • 可以提前处理出对应状态的棋子数目,避免重复计算

题目

poj1185

d[i][j][k] 表示前i行,第i行状态为$s_j$,第i-1行状态为$s_k$时最多能放的炮兵数
第i-2行状态为$s_l$,当前行的炮兵数目为$c_j$

$$d_{i,j,k} = Max(d_{i-1,k,l}) + c_j$$

覆盖模型

给定一个m*n的棋盘,放入各种形状的图形,问铺满方案

注意

  • 确定隐含条件 m*n<=100 max(min(m,n)) = 10
  • 确定状态转移的关系图,当关系较多无法存储时直接dfs转移

题目

poj2411(uva11270) 求1*2的骨牌覆盖m*n的矩形的方案

我们设m<=n,首先确定可以铺满的充要条件是m,n中至少有一个为偶数。

然后对两行状态dfs,p为当前列,s1为当前行状态,s2为上一行状态

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int p,int s1,int s2)
{
if(p>m)
{
ST[0].push_back(s1);
ST[1].push_back(s2);
//G[s1][s2] = 1;
return ;
}
dfs(p+1,s1<<1|1,s2<<1); //竖放,必要条件是s2未被占
dfs(p+1,s1<<1,s2<<1|1); //不放,必要条件是s2已被占
if(p<=m-1) dfs(p+2,s1<<2|3,s2<<2|3);//横放,必要条件是s2的两格已被占
}

然后根据状态递推, $d_{i,s}$ 表示当前行状态为s,且前i-1行铺满的方案数
$$\begin{cases}
d_{0,2^m-1} = 1 \\
d_{i,s1} = \sum d_{i-1,s2} \;\; (s1,s2) 配对
\end{cases}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
memset(d,0,sizeof d);
d[0][(1<<m)-1] = 1;

for(int i=1;i<=n;++i)
{
int t=i&1;
for(int i=0;i<S[0].size();++i)
{
d[t][S[0][i]] += d[t^1][S[1][i]];
}
memset(d[t^1],0,sizeof (d[t^1]));
}

printf("%d\n",d[n&1][(1<<m)-1]);

hihocoder 骨牌问题三连发

当n非常大时,就要用到矩阵快速幂
首先构造状态图的邻接矩阵,即上面dfs中的G
我们知道$G^k_{(i,j)}$ 表示从i到j 的所有长度为k的路径数
则最后答案为$G^n_{2^m-1,2^m-1}$,因为状态转移为每行间的,一共有n行,则表示从最开始到最后铺满的方案数。

sgu131 多了一种L形骨牌,dfs略有不同

dfs(p,s1,s2,b1,b2) b1,b2表示上一列放置对当前两行的影响(1,0)
来看状态:
sgu131

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void dfs(int p,int s1,int s2,int b1,int b2) 
{
if(p>m)
{
if(!b1 && !b2)
{
ST[0].push_back(s1);
ST[1].push_back(s2);
//G[s1][s2] = 1;
}
return;
}

//00
//00
dfs(p+1,s1<<1|b1,s2<<1|(1^b2),0,0);
//00
//11
if(b1==0) dfs(p+1,s1<<1|1,s2<<1|(1^b2),1,0);
//10
//10
if(b1==0 && b2==0) dfs(p+1,s1<<1|1,s2<<1,0,0);
//10
//11
if(b1==0 && b2==0) dfs(p+1,s1<<1|1,s2<<1,1,0);
//01
//11
if(b1==0) dfs(p+1,s1<<1|1,s2<<1|(1^b2),1,1);
//11
//01
if(b2==0) dfs(p+1,s1<<1|b1,s2<<1,1,1);
//11
//10
if(b1==0 && b2==0) dfs(p+1,s1<<1|1,s2<<1,0,1);
}

高能

由于状态矩阵十分稀疏,普通的矩阵快速幂开销太大

矩阵快速幂优化

1
2
3
4
5
6
7
8
9
10
11
12
13
void mul(Matrix A,Matrix B,Matrix res)
{

memset(C,0,sizeof C);
for(int i=0;i<sz;++i)
for(int j=0;j<sz;++j)
{
if(A[i][j]==0) continue; //这里改变了以往矩阵乘法的顺序
for(int k=0;k<sz;++k)
C[i][k] = (C[i][k] + A[i][j]*B[j][k]) % mod;
}
memcpy(res,C,sizeof(C));
}

经过上述优化

  • hihocoder1162 820ms -> 132ms
  • m=10,n=2147483647,54.385s

稀疏矩阵乘法

用三元组(i,j,v)来存储矩阵,矩阵中的0较多时可以提升效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void mul(Matrix A,Matrix B,Matrix res)
{
a.clear();
b.clear();

memset(C,0,sizeof C);
memset(hq,-1,sizeof hq);

for(int i=0;i<sz;++i)
for(int j=0;j<sz;++j)
{
if(A[i][j]) a.push_back(mat(i,j,A[i][j]));
if(B[i][j])
{
if(hq[i]==-1) hq[i] = b.size();
b.push_back(mat(i,j,B[i][j]));
}
}
// for(int i=0;i<b.size();++i) printf("%d %d %d\n",b[i].i,b[i].j,b[i].v);
// for(int i=0;i<sz;++i) printf("%d\n",hq[i]);

for(int i=0;i<a.size();++i)
{
if(hq[a[i].j]==-1) continue;
for(int j=hq[a[i].j]; j<b.size();++j)
{
if(b[j].i!=a[i].j) break;
C[a[i].i][b[j].j] = (C[a[i].i][b[j].j] + a[i].v*b[j].v) % mod;
}
}

memcpy(res,C,sizeof(C));
}

经过上述优化

  • hihocoder1162 132ms -> 77ms
  • m=10,n=2147483647,46.649s

p.s. 上述程序编译过程中未开任何优化,加上O2优化可以在20s内得出结果

推广

若骨牌变为1*r

首先可以确定能覆盖满的充要条件为 r|m*n
递推关系仍为上面的式子,表示前i-2行覆盖满,第i行和第i-1行状态为s1, (s1,s2)匹配
就要用到r进制了,r进制中0..r-1分别表示从上至下1的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int p,int s1,int s2)
{
if(p>r)
{
d[i][s1] += d[i-1][s2];
//ST[0].push_back(s1);
//ST[1].push_back(s2);
//G[s1][s2] = 1;
return;
}
for(int i=0;i<r;++i) //竖(不)放,以三进制为例 s1 0 1 1 s2 1 1 0
dfs(p+1,s1*r+i,s2*r+(i+1)%r);
if(p<=m-r+1)
dfs(p+r,s1*qpow(r,r)+qpow(r,r)-1,p*qpow(r,r)+qpow(r,r)-1); //横放 1 1 1
}

//d[0][qpow(r,m)-1] = 1;
//ans = d[n][qpow(r,m)-1];

参考