[SCOI2005]互不侵犯
题意简明易懂，就不多做解释了。
那么这道题怎么做呢？
可以明确的一点是：这是一道状压dp
因为这篇文章主要讲的是状态压缩，所以dp方程就不具体推了
我们建立dp[i][j][k]来存储第i行第j个状态，且放了k个国王的方案数
第一步，列出所有可能成立的单行状态
因为国王可以攻击到左右两格，所以可以通过上面的(a&(a<<1))||(a&(a>>1))来排除一些不可能成立的状态
我们将所有成立的状态存储到一个数组里便于取用
注意全0状态也算进去
第二步，初始化
先列出第一行每一种状态的方案数，以便于后面的dp使用
第三部：动规
枚举i,j,l,k，这里l指第i-1行的状态是第l种，j指第i行的状态是第j种，并且排除掉上下行的国王可以互相攻击到的情况
用a代表j状态，b代表l状态
排除方法：if((a&b)||(a&(b<<1))||(a&(b>>1)))continue;
接下来再通过dp[i][j][k]+=dp[i-1][l][k-sum(a)]的dp方程求出最终要求的方案数，这里sum(a)指a在二进制下1的个数
code：
#include <cstdio> #include <iostream> using namespace std; int n,k,a,b,tot,use[1001]; long long dp[11][1001][101]; long long ans; int sum(int s){ int num=0; while(s){ if(s%2)num++; s/=2; } return num; } int main(){ scanf("%d%d",&n,&k); for(int i=0;i<=(1<<n)-1;i++) if(!(i&(i>>1)))use[++tot]=i; for(int i=1;i<=tot;i++){ dp[1][i][sum(use[i])]=1; } for(int i=2;i<=n;i++){ for(int j=1;j<=tot;j++){ for(int t=1;t<=tot;t++){ a=use[j],b=use[t]; if((a&b)||(a&(b<<1))||(a&(b>>1)))continue; for(int p=sum(a);p<=k;p++){ dp[i][j][p]+=dp[i-1][t][p-sum(a)]; } } } } for(int i=1;i<=tot;i++){ ans+=dp[n][i][k]; } printf("%lld\n",ans); return 0; }
最后别忘了long long哦~
类型题推荐：
如有问题和错误，请各位尽情提出，感激不尽~