[SCOI2005]互不侵犯 (状压$dp$)

题目链接

Solution

状压 $dp$ .

$f[i][j][k]$ 代表前 $i$ 列中 , 已经安置 $j$ 位国王,且最后一位状态为 $k$ .

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

记忆化搜索还是不够啊... 只能会正向 $dp$ .

Code

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll f[10][101][1100],n,K;

ll js[1100],sum,ans;

int main()

{

	cin>>n>>K;

	sum=(1<<n)-1;

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

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

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

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

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

	else 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<<1&kk))continue;

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

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

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

		}

	}

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

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

	cout<<ans<<endl;

}

巴特西

[SCOI2005]互不侵犯 (状压$dp$)

题目链接

Solution

Code

最新文章

热门文章