P1879&&ybtoj【動态規劃】5章1題【Corn Fields G】

Corn Fields G

題目

P1879

解析

發現邊長<=12，考慮狀壓DP，為了友善隻存儲可行方案，設dp[i][j]為處理到第i行，使用第j個方案時的總方案個數，s[i]為第i個方案，a[i]為第i行的地形(可行為1,不可行為0)，顯然有動态轉移方程(省去取模，且tot為總方案數，并設f(x,y)為x&y)：

d p 0 , 1 = 1 dp_{0,1}=1 dp0,1​=1

d p i , j = ∑ d p i − 1 , k ( 1 < = i < = n , 1 < = j < = t o t , 1 < = k < = t o t ) dp_{i,j}=∑dp_{i-1,k}(1<=i<=n,1<=j<=tot,1<=k<=tot) dpi,j​=∑dpi−1,k​(1<=i<=n,1<=j<=tot,1<=k<=tot)

f s j , s k = = 0 f_{s_j,s_k}==0 fsj​,sk​​==0

即兩行不能有相鄰

f s j , a i = = s j f_{s_j,a_i}==s_j fsj​,ai​​==sj​

f s k , a i − 1 = = s k f_{s_k,a_{i-1}}==s_k fsk​,ai−1​​==sk​

即兩行方案必須合法

a n s = ∑ d p n , i ( 1 < = i < = t o t ) ans=∑dp_{n,i}(1<=i<=tot) ans=∑dpn,i​(1<=i<=tot)

即所有合法結果

code:

#include<cstdio>
#include<iostream>
#define rr register int
#define int long long
#define mod 100000000
using namespace std;
int n,m,dp[13][378],a[13],x,ans,tot,s[378];
signed main()
{
	scanf("%lld%lld",&n,&m),dp[0][1]=1;
	for(rr i=1;i<=n;++i)for(rr j=1;j<=m;++j)scanf("%lld",&x),a[i]=a[i]<<1|x;
	for(rr i=0;i<(1<<m);++i)if(!(i&(i<<1)))s[++tot]=i;
	for(rr i=1;i<=n;++i)
	 for(rr j=1;j<=tot;++j)
	  if((s[j]&a[i])==s[j])
	   for(rr k=1;k<=tot;++k)
	    if((!(s[j]&s[k]))&&((s[k]&a[i-1])==s[k]))
	     dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
	for(rr i=1;i<=tot;++i)ans=(ans+dp[n][i])%mod;
	printf("%lld",ans);
	return 0;
}