第七课轮廓线dp

B 铺砖问题

解法

这道题我们可以使用 $dp$。

我们可以在每一行枚举轮廓，逐格转移。

我们看上图，我们现在考虑的是红星位置的三种情况：横，竖和不放。

因为后面无论怎么放都不可能填满红色部分，所以红色部分都必须满。

那么，如果红星的上面没有填，那么必须填。

相反，如果红星的上方没填，那么就可以横放或者不放。

那么使用二进制压缩这条轮廓，然后滚动数组转移就好了。

具体详见代码。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[2][4096];
int n,m;

signed main()
{
	scanf("%d%d",&n,&m);
	dp[0][(1<<m)-1]=1;
	int cur=1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)//逐格转移
		{
			cur^=1;
			for(int mask=0;mask<(1<<m);mask++)//枚举所有状态
			{
				if(dp[cur][mask])
				{
					if(!(mask>>j&1)) dp[cur^1][mask|(1<<j)]+=dp[cur][mask];//如果上面没放则必须放。
					else
					{
						if(j>0 && !(mask>>(j-1)&1)) dp[cur^1][mask|(1<<(j-1))]+=dp[cur][mask];//如果左边没放就放左边
						dp[cur^1][mask^(1<<j)]+=dp[cur][mask];//不放，要把这个状态1变成0表示没放
					}
                }
			}
			memset(dp[cur],0,sizeof dp[cur]);
		}
	}
	printf("%lld",dp[cur^1][(1<<m)-1]);
}

B铺砖问题II

解法

这道题有了 $1 \times 1$ 方块数量的限制，所以我们可以多加一维，$f_{cur,mask,k}$ ，表示滚动数组，轮廓线状态和 $1\times1$ 砖块使用个数。

那么分几种情况：

  1. 上面已填，那么这个格子可以填 $1\times 1$ 的砖块。
  2. 上面已填，左边未填，那么可以横着放。
  3. 上面未填，填上面的。
  4. 上面已填，空着放。

值得注意的是，第三和第四种可以用一个异或操作合并成一条转移方程：

$f_{cur\oplus1,mask\oplus{2^j},k}+=f_{cur,mask,k}$

因为如果上面有填，那么这个格子放空，也就是异或之后就会变成 $0$。

相反，如果上面未填，那么异或就会将其变成 $1$，也就是填满。

代码

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
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 7;
int dp[2][4096][22];
int n,m,c,d;
char mp[123][123];
int main()
{
	scanf("%d%d%d%d",&n,&m,&c,&d);
	for(int i=0;i<n;i++) scanf("%s",mp[i]);
	dp[0][(1<<m)-1][0]=1;
	int cur=1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cur^=1;
			for(int k=0;k<=d;k++)
			{
				for(int mask=0;mask<1<<m;mask++)
				{
					if(mp[i][j]=='1')
					{
						if(mask&(1<<j)) dp[cur^1][mask][k+1]+=dp[cur][mask][k],dp[cur^1][mask][k+1]%=inf;
						if(j>0 && !(mask&(1<<(j-1))) && mask&(1<<j)) dp[cur^1][mask|(1<<(j-1))][k]+=dp[cur][mask][k],dp[cur^1][mask|(1<<(j-1))][k]%=inf;
						dp[cur^1][mask^(1<<j)][k]+=dp[cur][mask][k];
						dp[cur^1][mask^(1<<j)][k]%=inf;
					}
					else 
					{
						if(mask&(1<<j)) dp[cur^1][mask][k]+=dp[cur][mask][k],dp[cur^1][mask][k]%=inf;
                    }
				}
			}
			memset(dp[cur],0,sizeof dp[cur]);
		}
	}
	long long ans=0;
	for(int i=c;i<=d;i++) ans+=dp[cur^1][(1<<m)-1][i],ans%=inf;
	cout<<ans;
}