状态压缩dp入门

首先一次搜索，确定哪些状态能行，对应的国王数量是多少，然后再把放置到第多少行，状态是什么，国王数量是多少对应的方案数算出来，这就需要先确定状态，再通过状态转移求解。

dp[i][j][k]表示第I行，状态j，k个国王
并且去除掉相邻行的状态，再转移
最后把n行k个国王，所有的状态方案数总和算出来即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[11][999][85];
int sta[999];
int sumk[999];
int n,k;
int cnt=0;
void dfs(int state,int cur,int num)
{
    if(cur>=n)
    {
        sta[++cnt]=state;
        sumk[cnt]=num;
        return;
    }
    dfs(state|(1<<cur),cur+2,num+1);
    dfs(state,cur+1,num);
}
void dp_init()
{
    for(int i=1;i<=cnt;i++)
    {
        dp[1][i][sumk[i]]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cnt;j++){
            for(int l=1;l<=cnt;l++){
                if(sta[l]&sta[j]) continue;
                if((sta[l]<<1)&sta[j]) continue;
                if((sta[l]>>1)&sta[j]) continue;
                for(int p=sumk[l];p<=k;p++){
                    dp[i][l][p]+=dp[i-1][j][p-sumk[l]];
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    dfs(0,0,0);
    dp_init();
    ll ans=0;
    for(int i=1;i<=cnt;i++)
    {
        ans+=dp[n][i][k];
    }
    printf("%lld\n",ans);
}