51nod-1033 骨牌覆盖 V2

地址：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1033

思路：状态压缩DP+矩阵快速幂

对于每行最多只有5列，因此可以枚举出它们的全部状态 0->(1<<m)-1,对于状态其二进制1表示已经有骨牌覆盖，0表示没有，

1.由于是1X2的骨牌，则二进制数11,110是合法的，1,10是不合法的，那么其合法的状态只有d{0,3,6,12,15,24,27,30}

2.对于第i行的状态只与第i-1行的状态有关，那么对于第i-1行的状态a中二进制位为0的就必须要在第i行的状态b中补上，

例如a=5(101) 那么b=3(11)是合法的, b=1是不合法的，因为b=1,101和001是不可以将中间的0给补上，而b=3则是将 2*1的骨牌插在中间，因此对于第i行状态b来说 a|b=(1<<m)-1才是合法的

3.同时 a&b必须在合法状态中才行，因为a&b表示第i行的1*2的骨牌的摆放状态，例如二进制 a=1011,b=1110,这时 a&b=1010而此时的骨牌是没法摆放的

4.那么此时就可以写出状态压缩DP了

		dp[1][0]=dp[1][3]=dp[1][6]=dp[1][12]=dp[1][15]=dp[1][24]=dp[1][27]=dp[1][30]=1;
		int s=(1<<m)-1;
		for(int i=2;i<=n;++i)
			for(int j=0;j<=s;++j)
				for(int k=0;k<=s;++k)
					if((j|k)==s&&d[j&k])
						dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;

时间复杂度为 O(n*pow(2,5)*pow(2,5))是肯定超时的

而我们对转移方程观察发现

dp[i][j]只与 dp[i-1][k]有关，而对于判断条件 if((j|k)==s&&d[j&k]) 也是固定的

那么就可以用矩阵快速幂来优化.

Code 状态压缩DP版本:

#include<iostream>
#include<cstring>
using namespace std;

const int MOD=1e9+7;
const int MAX_N=1005;
int n,m;
bool d[35];
int dp[MAX_N][35];

int main()
{
	ios::sync_with_stdio(false);
	d[0]=d[3]=d[6]=d[12]=d[15]=d[24]=d[27]=d[30]=1;
	while(cin>>n>>m){
		memset(dp,0,sizeof(dp));
		dp[1][0]=dp[1][3]=dp[1][6]=dp[1][12]=dp[1][15]=dp[1][24]=dp[1][27]=dp[1][30]=1;
		int s=(1<<m)-1;
		for(int i=2;i<=n;++i)
			for(int j=0;j<=s;++j)
				for(int k=0;k<=s;++k)
					if((j|k)==s&&d[j&k])
						dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
		cout<<dp[n][s]<<endl;
	}
	
	return 0;
}

Code 状态压缩DP+矩阵快速幂优化:

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;

const int MOD=1e9+7;
const int MAX_S=35;
struct Matrix{
	LL a[MAX_S][MAX_S];
	Matrix (){	memset(a,0,sizeof(a));}
	Matrix operator*(const Matrix &A){
		Matrix B=Matrix();
		for(int k=0;k<MAX_S;++k)
			for(int i=0;i<MAX_S;++i)
				for(int j=0;j<MAX_S;++j)
					B.a[i][j]=(B.a[i][j]+a[i][k]*A.a[k][j])%MOD;
		return B;
	}
};
int n,m;
int d[MAX_S];

int main()
{
	ios::sync_with_stdio(false);
	d[0]=d[3]=d[6]=d[12]=d[15]=d[24]=d[27]=d[30]=1;
	while(cin>>n>>m){
		int s=(1<<m)-1;
		Matrix res=Matrix(),A=Matrix();
		for(int i=0;i<=s;res.a[i][i]=1,++i)
			for(int j=0;j<=s;++j)
				if((i|j)==s&&d[i&j])
					A.a[i][j]=1;
		while(n){
			if(n&1)	res=res*A;
			A=A*A;
			n>>=1;
		}
		cout<<res.a[s][s]<<endl;
	}
	
	return 0;
}

51nod-1033 骨牌覆盖 V2

相关推荐