【bzoj1087】互不侵犯King 状态压缩dp

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=1087

【题解】

用f[i][j][k]表示前i行放了j个棋子且第i行的状态为k的方案数。

vis[i]表示状态i是否合法，check[i][j]表示状态i，j是否可以相邻。

详见代码：

/*************

  bzoj 1087

  by chty

  2016.11.15

*************/

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long ll;

#define FILE "read"

#define up(i,j,n) for(ll i=j;i<=n;i++)

namespace INIT{

	char buf[1<<15],*fs,*ft;

	inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}

	inline ll read() {

		ll x=0,f=1;  char ch=getc();

		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}

		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}

		return x*f;

	}

}using namespace INIT;

ll n,m,ans,vis[1<<9],sum[1<<9],check[1<<9][1<<9],f[11][121][1<<9];

void pre(){

	up(i,0,(1<<n)-1)if(!(i&(i<<1))){vis[i]=1; for(ll x=i;x;x>>=1)  sum[i]+=(x&1);}

	up(i,0,(1<<n)-1){

		if(!vis[i])  continue;

		up(j,0,(1<<n)-1){

			if(!vis[j]||(i&j)||(i&(j>>1))||(j&(i>>1)))  continue;

			check[i][j]=1;

		}

	}

}

int main(){

	freopen(FILE".in","r",stdin);

	freopen(FILE".out","w",stdout);

	n=read();  m=read();

	pre();  up(i,0,(1<<n)-1) if(vis[i]) f[1][sum[i]][i]=1;

	up(i,2,n)up(j,0,(1<<n)-1){

		if(!vis[j])  continue;

		up(k,0,(1<<n)-1){

			if(!vis[k]||!check[j][k])  continue;

			up(p,sum[k],m-sum[j])  f[i][p+sum[j]][j]+=f[i-1][p][k];

		}

	}

	up(i,0,(1<<n)-1)  ans+=f[n][m][i];

	printf("%lld\n",ans);

	return 0;

}

巴特西

【bzoj1087】互不侵犯King 状态压缩dp

最新文章

热门文章