[SCOI2005]互不侵犯（状压Dp）

题目

原题

Solution

看到数据范围就可以想到状压，然后你就可以直接转移就好了？

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<queue>
#include<algorithm>
#define ll long long
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
using namespace std;
inline int gi(){
	int sum=0,f=1;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
inline ll gl(){
	ll sum=0,f=1;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
int have(int s){
	int ans=0;
	while(s){
		if(s&1)ans++;s>>=1;
	}
	return ans;
}
int n,siz[2010],gs[2010],cnt;
ll dp[12][2010][101];
void dfs(int i,int s,int sum){
	if(i>=n){
		siz[++cnt]=s;
		gs[cnt]=sum;
		return;
	}
	dfs(i+1,s,sum);
	dfs(i+2,s+(1<<i),sum+1);
}
int main(){
    int i,j,k,m;
	n=gi();k=gi();
	dfs(0,0,0);
	//设dp[i][j][k]表示第i行的放置方案为j,总共放了k个的方案总数.
	//dp[i][j][k]+=dp[i-1][m][k-have(j)];
	for(i=1;i<=cnt;i++)
		dp[1][i][gs[i]]=1;
	for(i=2;i<=n;i++)
		for(j=1;j<=cnt;j++)
			for(int kk=1;kk<=cnt;kk++){
				if(siz[j]&siz[kk])continue;
				if((siz[j]<<1)&siz[kk])continue;
				if(siz[j]&(siz[kk]<<1))continue;
				for(int jj=k;jj>=gs[j];jj--)
					dp[i][j][jj]+=dp[i-1][kk][jj-gs[j]];
			}
	ll ans=0;
	for(j=1;j<=cnt;j++)
		ans+=dp[n][j][k];
	printf("%lld
",ans);
	return 0;
}