SMOJ 种植玉米/铺地砖 题解

最近练了轮廓线dp的题目

1.种植玉米

题意

农夫有一个被划分成$m$行$n$列的农田。

每个格子的数字如果是$1$则表示该格子的土地是肥沃的，可以种植玉米；如果该格子的数字是$0$则表示该格子不能种植玉米。

但是还有一个条件：不能出现相邻的两个格子都种植玉米的情况。

问有多少种不同的种植方式。

$1\le m,n\le 15$

思路

前一篇题解的经验告诉我们，我们同样的使用记忆化搜索实现这个轮廓线dp。

但是在这一题中，如果我们一行一行从左向右填，我们既要考虑正上方的状态也要考虑左边的状态。

于是我们就要对状态$s$进行一些改动：设当前遍历到了$r$行$c$列的格子，$0$不填$1$填。$s$的$1\sim c-1$位表示$r$行$1\sim c-1$的状态，$s$的$c$到最后一位表示$r-1$行的$c$到最后一位的状态（因为$r-1$行的$1\sim c-1$位对当前没有影响）。

钦定一下下面代码用到的状态：

int t=(1<<(c-1)),pt=(1<<(c-1-1));//上、左 

如果不能种，强制修改当前位为$0$并转移。

if(!a[r][c])//不能种 
{if(s&t)f[r][c][s]=dfs(r,c+1,s^t);else f[r][c][s]=dfs(r,c+1,s);return f[r][c][s];
}

如果能种，那么既可以种，也可以不种，那么先看不种：其实和刚刚一样的，同样强制修改为$0$并转移，不过不能直接return，因为要累加到当前格子的贡献去。

如果种的话，就要满足$c$位（上方）位$0$，且$s$的$c-1$位（左侧）状态为$0$，或者说本身就在第一列。此时需要把本位$c$的状态强制修改为$1$。

int z=0,bz=0;
//不种
if(s&t)bz=dfs(r,c+1,s^t);
else bz=dfs(r,c+1,s);
//种
if(!(s&t)&&(!(s&pt)||c==1))z=dfs(r,c+1,s|t);

代码

#include<bits/stdc++.h>
using namespace std;
const int N=16,M=16,inf=0x3f3f3f3f,mod=1e8;
int n,m,a[N][M];
int f[N][M][1<<(M-1)+3];
int dfs(int r,int c,int s)//状态s:r行1~c-1位状态，r-1行c~m位状态 
{if(r>n)return 1;if(c>m)return dfs(r+1,1,s);if(!(f[r][c][s]>=inf))return f[r][c][s];int t=(1<<(c-1)),pt=(1<<(c-1-1));//上、左 if(!a[r][c])//不能种 {if(s&t)f[r][c][s]=dfs(r,c+1,s^t);else f[r][c][s]=dfs(r,c+1,s);return f[r][c][s];}int z=0,bz=0;//不种if(s&t)bz=dfs(r,c+1,s^t);else bz=dfs(r,c+1,s);//种if(!(s&t)&&(!(s&pt)||c==1))z=dfs(r,c+1,s|t);f[r][c][s]=(bz+z)%mod;return f[r][c][s];
}
int main()
{scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];memset(f,inf,sizeof(f));printf("%lld",dfs(1,1,0));return 0;
}

2.铺地砖

题意

$1\le h,w\le 16$

答案对$10^9+7$取模。

思路

把影响修改一下，变成1x2或者2x1的地砖即可。

对于状态$s$，$0$表示没填$1$表示填了，$s$的$1\sim c-1$位表示$r$行$1\sim c-1$的状态，$s$的$c$到最后一位表示$r-1$行的$c$到最后一位的状态（因为$r-1$行的$1\sim c-1$位对当前没有影响）。

当前格是$(r,c)$，钦定一下状态

int t=(1<<(c-1)),nt=(1<<(c+1-1));//上、右

如果填了就要把当前位强制修改为$0$

if(s&t)//利用已有的竖线or横线 
{f[r][c][s]=dfs(r,c+1,s^t);return f[r][c][s];
}

否则填地砖，打竖需要$r<n$，打横需要下一个没填且$c<m$。

int shu=0,heng=0;if(r<n)shu=dfs(r,c+1,s|t);if(c<m&&!(s&nt))heng=dfs(r,c+1,s|nt);

代码

#include<bits/stdc++.h>
using namespace std;
const int N=17,M=17,inf=0x3f3f3f3f,mod=1e9+7;
int n,m;
int f[N][M][1<<M];
int dfs(int r,int c,int s)//状态s:r行1~c-1位状态，r-1行c~m位状态 
//0表示没填，1表示填过 
{if(r>n)return 1;if(c>m)return dfs(r+1,1,s);if(!(f[r][c][s]>=inf))return f[r][c][s];int t=(1<<(c-1)),nt=(1<<(c+1-1));if(s&t)//利用已有的竖线or横线 {f[r][c][s]=dfs(r,c+1,s^t);return f[r][c][s];}int shu=0,heng=0;if(r<n)shu=dfs(r,c+1,s|t);if(c<m&&!(s&nt))heng=dfs(r,c+1,s|nt);f[r][c][s]=(shu+heng)%mod;return f[r][c][s];
}
int main()
{scanf("%d%d",&n,&m);if((n*m)&1){puts("0");return 0;}memset(f,inf,sizeof(f));printf("%lld",dfs(1,1,0));return 0;
}