P1896 [SCOI2005]互不侵犯

状压DP。
分析：

这是一道典型的状压$DP$。

看题目，显然这题搜索过不了，选择DP；看数据范围： $1 <=N <=9, 0 <= K <= N * N$ 选择状压$DP$

可以用一个$n$位的二进制数来保存每一行的状态：如果这个二进制位上是$1$则放了国王，是$0$则没放国王

在$DP$时从第一行推到最后一行

设$dp[i][j][k]$表示前$i$行放了$j$个国王第$i$行的状态是$k$（实际上$k$表示的是可行的状态集合中的第$k$个状态）的方案数

预处理所有满足条件的状态：即状态中没有相邻两位都是$1$，这里可以用(i&(i<<1))==0来判定（即将$i$左移一位，如果存在相邻两位都是$1$的话，1&1=1，则i&(i<<1)就不等于$0$了）

预处理此状态下放置的国王数目：就是统计此状态中$1$的数目，方便后续转移时直接用

预处理满足条件的上下两行：题目要求本格如果放国王的话，本格的左上和右上的格子不允许放国王：

这是比较直观的写法：((rt[i]&rt[j])==0)&&(((rt[i]<<1)&rt[j])==0)&&(((rt[i]>>1)&rt[j])==0)

这是比较好一点的写法：((rt[i]&rt[j])==0)&&(((rt[i]|rt[j])&((rt[i]|rt[j])<<1))==0)

解释：(i&(i<<1))==0是我们熟悉的判定$i$状态是否存在相邻的两位都是$1$，因为$i$和$j$都是满足条件的（即不存在相邻两位都是$1$，且不存在在同一位置上的数都是1），所以：

那么就存在相邻两位都是1的情况了所以此时的$i,j$不是满足条件的上下两行

接下来赋初始值

$dp[1][nm[i]][i]=1;$

其中i是满足条件的状态的编号

$dp[0~n][0][1]=1;$

其中第一个可行的状态即一个国王都不放

具体细节见代码

#include <bits/stdc++.h>
#define ll long long
#define maxn 10
using namespace std;
ll n,k,lg,rt[1<<maxn],ok[1<<maxn][1<<maxn],nm[1<<maxn],dp[maxn][maxn*maxn][1<<maxn],ans;
inline ll read(){
    ll x=0,f=0;
    char c=getchar();
    while(!isdigit(c))
        f|=c=='-',c=getchar();
    while(isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}
int main(){
    n=read();k=read();
    lg=1<<n;
    for(register int i=0;i<lg;++i)//找出所有满足条件的状态 
        if((i&(i<<1))==0)
            rt[++rt[0]]=i;
    for(register int i=1;i<=rt[0];++i)
        for(register int j=1;j<=n;++j)
            if(rt[i]&(1<<(j-1)))//统计出每个状态中1的个数 
                ++nm[i];
    for(register int i=1;i<=rt[0];++i)//附初始值 
        dp[1][nm[i]][i]=1;
    for(register int i=0;i<=n;++i)//附初始值 
        dp[i][0][1]=1;
    for(register int i=1;i<=rt[0];++i)
        for(register int j=1;j<=rt[0];++j)
            if(((rt[i]&rt[j])==0)&&(((rt[i]|rt[j])&((rt[i]|rt[j])<<1))==0))//寻找满足条件的上下两行的状态 
                ok[i][++ok[i][0]]=j;
    for(register int h=2;h<=n;++h)//第几行 
        for(register int kg=1;kg<=k;++kg)//放了几个国王 
            for(register int i=1;i<=rt[0];++i)//在可行状态里面找 
                if(kg>=nm[i]) 
                    for(register int j=1;j<=ok[i][0];++j)//在可行的上一行状态里面找 
                        if(kg>=nm[i]+nm[ok[i][j]])
                            dp[h][kg][ok[i][j]]+=dp[h-1][kg-nm[ok[i][j]]][i];//状态转移 
    for(register int i=1;i<=rt[0];++i)
        ans+=dp[n][k][i];//统计答案 
    printf("%lld\n",ans);
    return 0;
}