洛谷原題鏈接:P10975 Mondriaan's Dream
看數(shù)據(jù)范圍容易發(fā)現(xiàn)是狀壓DP
考慮如何規(guī)定狀態(tài)
設(shè)f(i,s)為第i行,填充格式為s的方案數(shù),其中s為二進(jìn)制數(shù),1表示在這個(gè)位置填充一個(gè)長(zhǎng)方形并使它延伸到i+1(即以i為起點(diǎn)的兩行一列的長(zhǎng)方形),0表示由i-1延伸而來(lái)或填充一個(gè)長(zhǎng)方形并使它不延伸到i+1(即在第i行放置一行兩列的長(zhǎng)方形)
轉(zhuǎn)移方程很簡(jiǎn)單,dp(i,s1)= dp(i-1, s2)+1,關(guān)鍵在于如何判斷 s1和s2是否合法
合法性判斷:
- 如果i-1的第j位為1,代表j是一個(gè)延伸到i的長(zhǎng)方形,所以i的第j位就一定是由i-1的第j位填充的,即 s1 & s2 == 0
- 對(duì)于s1,被s2填充延伸部分填充之后,不能存在一段連續(xù)奇數(shù)個(gè)0的序列(無(wú)法使用兩格的長(zhǎng)方形填充),即 s1 | s2 之后判斷
// x=s1 | s2;
// w=s1.size();
bool check(int x,int w)
{
bool flag=0;
for(int j=0;j<w;j++)
{
if(!((1<<j) & x))
{
if(!flag) flag=1;
else flag=0;
}
else if(flag) return 0;
}
if(flag) return 0;
return 1;
}
- 考慮邊界的判斷,即當(dāng)i=n時(shí),s1只能等于0(無(wú)法向后面延伸)
代碼:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int const N=(1<<11);
int dp[12][N];
int n,m;
bool check(int x,int w)
{
bool flag=0;
for(int j=0;j<w;j++)
{
if(!((1<<j) & x))
{
if(!flag) flag=1;
else flag=0;
}
else if(flag) return 0;
}
if(flag) return 0;
return 1;
}
int sovle (int h,int w)
{
if(h==1)
{
if(w%2) return 0;
else return 1;
}
int res=0;
memset(dp,0,sizeof(dp));
for(int i=0;i<(1<<w);i++) if(check(i,w)) dp[1][i]=1;
for(int i=2;i<=h;i++)
{
for(int now=0;now<(1<<w);now++)
{
for(int bs=0;bs<(1<<w);bs++)
{
if(now & bs) continue;
if(!check((now | bs),w)) continue;
dp[i][now]+=dp[i-1][bs];
}
if(i==h) break;
}
}
for(int i=0;i<(1<<w);i++) res+=dp[h][i];
return res;
}
signed main(){
cin>>n>>m;
while(n or m)
{
cout<<sovle(n,m)<<endl;
cin>>n>>m;
}
return 0;
}
浙公網(wǎng)安備 33010602011771號(hào)