一看数据范围，如果是枚举所有的棋盘情况，2^K，肯定超了，自然是要一行一行递推，而相邻这个情况用位运算会比较方便，所以用状压dp。
具体算法：dp[i][j][k]表示第i行，前i行有j个棋子，第i行的棋子情况。第一行初始化一下，符合条件的设为1.然后循环枚举出第i行，m总数的棋子，j的前一行状态，k的这一行状态，验证是否相邻，是否总数超过。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int N,K;
long long dp[100][100][1<<10]={0};
int count(int x)
{
int cnt=0;
while(x)
{
int t=x%2;
if(t)cnt+=1;
x/=2;
}
return cnt;
}
int main()
{
cin>>N>>K;
for(int i=0;i<1<<N;i++)
{
if(i&(i<<1)||count(i)>K)continue;
dp[1][count(i)][i]=1;
}
for(int i=2;i<=N;i++)
{
for(int m=0;m<=K;m++)
{
for(int j=0;j<(1<<N);j++)
{
for(int k=0;k<(1<<N);k++)
{
if(j&(j<<1)||k&(k<<1)||j&(k<<1)||(j<<1)&(k)||(j&k)||m<count(j)+count(k))continue;
dp[i][m][j]+=dp[i-1][m-count(j)][k];
}
}
}
}
long long ans=0;
for(int i=0;i<1<<N;i++)
{
ans+=dp[N][K][i];
}
cout<<ans;
return 0;
}
