CF845F - Guards In The Storehouse

题意：在 \((x,y)\) 放一个哨兵，可以监视本行后面的所有格子直到障碍、本列后面所有的格子直到障碍。求使全盘最多一个位置不被监视的方案总数。

我们发现，因为 \(nm\le 250\)，所以 \(\min(n,m)\le 15\)。我们选择较小的这个作为 \(n\)，另一个作为 \(m\) 进行状压。

设计状态 \(dp_{x,y,msk,i,j}\) 表示当前 \(dp\) 到位置 \((x,y)\)，\(msk_k=1\) 的行已经被左边的哨兵监视了，当前有/没有没有被监视的位置，当前位置有/没有被上面的哨兵监视。

我们的转移是：

如果当前是障碍，则把所有状态往 \(\{msk \wedge(2^{15}-1-2^{x}),i,0\}\) 转移。
如果当前是空地：

\[\begin{aligned}
\begin{cases}
\text{ 当前的位置自己填了}: dp_{msk,i,j}\rightarrow dp_{msk\vee(2^x),i,1}\\
\text{ 没填，当前的位置被上面的覆盖了}: dp_{msk,i,1}\rightarrow dp_{msk,i,1}\\
\text{ 没填，上面不能覆盖，被左边覆盖}: dp_{msk,i,0}[msk_x=1]\rightarrow dp_{msk,i,0}\\
\text{ 没填，没有被覆盖}: dp_{msk,0,0}[msk_x=0]\rightarrow dp_{msk,1,0}
\end{cases}
\end{aligned}\]

注意，这里存在一个问题，就是每一列 \(\text{dp}\) 结束之后要清空 \(j\)，但是这样就需要分类讨论。我们可以把矩阵设成 \(n+1\) 行，第 \(n+1\) 行都是障碍，这样更换列的时候就会天然把 \(j\) 清掉。

我们可以滚动掉 \(x\) 和 \(y\)，设计 \(dp\) 和 \(tmp\)，转移的时候从 \(dp\) 往 \(tmp\) 转移，结束之后把 \(tmp\) 复制到 \(dp\)，好处还在于 \(x\) 和 \(y\) 以及上一轮的 \(x'\) 和 \(y'\) 只存在于循环变量中，并不参与 \(dp\) 转移的过程。

const ll P=1000000007;

int n,m,a[255][255],b[255][255],p[255][255],cnt=0;

int dp[1<<16][2][2],tmp[1<<16][2][2];

st s;

signed main(){

	ios::sync_with_stdio(false);

	cin.tie(0);

	cin>>n>>m;

	rp(i,n){

		cin>>s;

		rp(j,m)if(s[j-1]=='.')a[i][j]=1;

	}

	if(n>m){

		swap(n,m);

		rp(i,n)rp(j,m)b[i][j]=a[j][i];

		rep(i,0,n+1)rep(j,0,m+1)a[i][j]=0;

	 	rp(i,n)rp(j,m)a[i][j]=b[i][j];

	}

	dp[0][0][0]=1;

	rp(y,m)rp(x,n+1){

		rd(i,1<<(n+2))rd(j,2)rd(k,2)tmp[i][j][k]=0;

		if(!a[x][y]){

			rd(msk,1<<(n+2))rd(j,2)rd(k,2)

				if(msk>>x&1)tmp[msk^(1<<x)][j][0]=(tmp[msk^(1<<x)][j][0]+dp[msk][j][k])%P;

				else tmp[msk][j][0]=(tmp[msk][j][0]+dp[msk][j][k])%P;

		}else{

			rd(msk,1<<(n+2))rd(j,2)rd(k,2)

				tmp[msk|(1<<x)][j][1]=(tmp[msk|(1<<x)][j][1]+dp[msk][j][k])%P;

			rd(msk,1<<(n+2))rd(j,2)

				tmp[msk][j][1]=(tmp[msk][j][1]+dp[msk][j][1])%P;

			rd(msk,1<<(n+2))rd(j,2)if(msk>>x&1)

				tmp[msk][j][0]=(tmp[msk][j][0]+dp[msk][j][0])%P;

			rd(msk,1<<(n+2))if(!(msk>>x&1))

				tmp[msk][1][0]=(tmp[msk][1][0]+dp[msk][0][0])%P;

		}

		rd(i,1<<(n+2))rd(j,2)rd(k,2)dp[i][j][k]=tmp[i][j][k];

	}

	int ans=0;

	rd(i,1<<(n+2))rd(j,2)rd(k,2)ans=(ans+dp[i][j][k])%P;

	cout<<ans<<endl;

	return 0;

}

//Crayan_r

巴特西

CF845F - Guards In The Storehouse

最新文章

热门文章