题目链接

https://ac.nowcoder.com/acm/problem/20240

解题思路

王者的讲解！！！看了特别多题解，只有这位巨佬的讲的最清楚

AC代码

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

using namespace std;
ll lowbit(ll x)
{
    return x&(-x);
}
const int N=(1<<10)+10;
const int M=10;
ll ans,n,k,cnt;
ll status[N],knum[N];
ll dp[M][N][M*M];
int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<(1<<n);i++)
    {
        if((i&(i<<1))) continue;找到每一行的可行状态
        status[++cnt]=i;
        ll x=i; 

        while(x>0)
        {
            knum[cnt]++;
            x-=lowbit(x);//树状数组的lowbit
        }

    }

    for(int i=1;i<=cnt;i++)
    {
        if(knum[i]>k) continue;
        dp[1][i][knum[i]]=1;
    }

    for(int i=2;i<=n;i++)//枚举行数 
    {
        for(int j=1;j<=cnt;j++)//枚举第j行的状态 
        {
            for(int p=1;p<=cnt;p++)//枚举第j-1行的状态 
            {
                if(status[j]&status[p]) continue;
                if(status[j]&(status[p]<<1)) continue;
                if((status[j]<<1)&status[p]) continue;

                for(int q=0;q<=k;q++)//j-1行及之前的状态用到的国王数量 
                {
                    if(q+knum[j]>k) break;
                    dp[i][j][knum[j]+q]+=dp[i-1][p][q];
                }
            }
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        ans+=dp[n][i][k];//第n行，共用k个国王，枚举所有状态之和
    }
    printf("%lld\n",ans);


}