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

Miku

真是自闭呢

这个题还是还理解的

dfs预处理出每一行的情况，然后dp

#include<iostream>
#include<cstdio>
using namespace std;
int ok[2001];
int n,kk;
long long dp[10][2001][2001];
int cou[2001];
int si[2001];
int cnt;
void dfs(int p,int co,int ns){
//	cout<<p<<endl;
	if(p>n){
		cnt++;
		ok[cnt]=ns;
		cou[cnt]=co;
		return ;
	}
	dfs(p+1,co,ns);
	dfs(p+2,co+1,ns+(1<<p));
	return ;
}
long long ans;
int main(){
	scanf("%d%d",&n,&kk);
	dfs(1,0,0);
	for(int i=1;i<=cnt;++i)
	{
		dp[1][i][cou[i]]=1;
	}
	for(int i=2;i<=n;++i){
		for(int j=1;j<=cnt;++j){
			for(int k=1;k<=cnt;++k){
				if((ok[j]&ok[k])==0){
					if(((ok[j]<<1)&ok[k])==0){
						if(((ok[j]>>1)&ok[k])==0){
							for(int z=kk;z>=cou[j];z--){
								dp[i][j][z]+=dp[i-1][k][z-cou[j]];
							}
						}
					}
				}
			}
		}
	}
	for(int i=1;i<=cnt;++i){
		ans+=dp[n][i][kk];
	}
	cout<<ans;
	return 0;

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

原文：https://www.cnblogs.com/For-Miku/p/13455664.html