题目链接

Solution

状压 \(dp\) .

\(f[i][j][k]\) 代表前 \(i\) 列中 , 已经安置 \(j\) 块草皮,且最后一位状态为 \(k\) .

同时多记录一个每一列中的不能放的位置 \(w[i]\).

然后就可以很轻松的转移了...

转移方程看代码.

Code

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll f[13][145][10000],n,K;

ll js[10000],m,sum,ans,w[14];

int main()

{

	cin>>n>>m;

	sum=(1<<m)-1;

	for(int i=1;i<=n;i++)

	for(int j=1;j<=m;j++)

	{

		int x; cin>>x;

		K+=x;

		w[i]=w[i]*2+x^1;

	}

	for(ll i=0;i<=sum;i++)

	for(ll j=0;j<m;j++)

	if(i&(1<<j))js[i]++;

	for(ll i=0;i<=sum;i++)

	{

		if((i<<1&i))continue;

		if((i&w[1]))continue;

		f[1][js[i]][i]=1;

	}

	for(ll i=1;i<n;i++)

	for(ll j=0;j<=K;j++)

	for(ll k=0;k<=sum;k++)

	{

		if(!f[i][j][k])continue;

		for(ll kk=0;kk<=sum;kk++)

		{

			if(kk&w[i+1])continue;

			if((k&kk)||(kk<<1&kk))continue;

			if(j+js[kk]>K)continue;

			f[i+1][j+js[kk]][kk]+=f[i][j][k];

		}

	}

	for(int j=0;j<=K;j++)

	for(ll i=0;i<=sum;i++)

	ans+=f[n][j][i];

	cout<<ans%100000000<<endl;

}