洛谷1896 [SCOI2005]互不侵犯

题意

在 $N\times N$ 的棋盘里摆 $k$ 个国王，每个国王可以攻击周围 $8$ 个格子，求国王互不侵犯的摆法有多少种。

其中 $N\le 9$ 。

题解

显然状压dp。可以预处理每一行的合法方案存在 $\text{s}[]$ ，合法方案即没有两个相邻的。

用 $\text{f}[i][j][k]$ 表示在第 $i$ 行，合法方案编号为 $j$ ，放了 $k$ 个棋子的方案数。枚举上一行的状态 $l$ ，转移方程为：

$$\text{f}[i][j][k]+=\text{f}[i-1][l][k-num[j]]$$

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll n,m,k,cnt,ans,f[15][1050][105],s[1050];

inline ll get_1(ll x)
{
    ll ans=0;
    while (x) x&=x-1,ans++;
    return ans;
}

int main()
{
    n=read(); k=read();
    m=1<<n;
    for (ll i=0;i<m;i++)
    {
        if (i&(i<<1)) continue;
        s[++cnt]=i;
        f[1][cnt][get_1(i)]=1;
    }
    for (ll i=2;i<=n;i++)
    {
        for (ll x=1;x<=cnt;x++)
        {
            for (ll y=1;y<=cnt;y++)
            {
                if (s[x]&s[y] || s[x]&(s[y]<<1) || s[x]&(s[y]>>1)) continue;
                ll num=get_1(s[x]);
                for (ll z=0;z<m;z++)
                {
                    if (z+num>k) break;
                    f[i][x][z+num]+=f[i-1][y][z];
                }
            }
        }
    }
    for (ll i=1;i<=cnt;i++) ans+=f[n][i][k];
    printf("%lld",ans);
    return 0;
}