在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

题目链接🔗

[SCOI2005]互不侵犯

题解

国王能攻击到周围9个格子
行列数据范围很小，我们可以压缩每行选取国王的情况
dp[i][j][k] 表示前 i 行，第 i 行摆法的压缩状态为 j 摆 k 个国王的摆法有多少种
为了不超时，先预先处理每行的状态数，保存起来，然后直接DP转移即可

代码

#include <cstdio>
using namespace std;
const int maxd = 2005;
long long dp[10][maxd][80];
long long map[maxd],num[maxd];
long long n,k,tot,ans;
void init()
{
    long long mx = (1<<n) - 1;

    for(int i=0;i<=mx;i++)
    {
        if(!((i<<1)&i))
        {
            map[++tot] = i;
            int t = i;
            while(t)
            {
                num[tot] += t&1;
                t >>= 1;
            }
            //printf("%lld",num[tot]);
        }
    }
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    scanf("%lld %lld",&n,&k);
    init();
    for(int i=1;i<=tot;i++)
        if(num[i]<=k) dp[1][i][num[i]] = 1;
    for(int i=2;i<=n;i++)	//当前行
        for(int j=1;j<=tot;j++) // 当前行的状态
            for(int p=1;p<=tot;p++)	// 下行状态
            {
                if(map[j]&map[p])continue;
                if(map[j]&(map[p]<<1))continue;
                if((map[j]<<1)&map[p]) continue;
                for(int s=1;s+num[j]<=k;s++)
                    dp[i][j][s+num[j]] += dp[i-1][p][s];
            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=tot;j++) ans += dp[i][j][k];
    printf("%lld",ans);	
    return 0;
}