原题链接
详解见题解区，个人见解见代码，蒟蒻真的折服于dalao的思路
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[20][210][1026]={0};
ll counts(int now)
{
ll ans=0;
while(now)
{
if(now&1)ans++;
now>>=1;
}
return ans;
}
ll check(ll x,ll y)
{
if(x & y)return 1;
if((x<<1) & y) return 1;
if((x>>1) & y) return 1;
return 0;
}
ll illegal(ll now)
{
if(now & (now>>1))return 1;
return 0;
}
int main()
{
ll n,k;
scanf("%lld%lld",&n,&k);
ll num=(1<<n)-1;
dp[0][0][0]=1;//什么都不放，方案是肯定是1
for(ll i=1;i<=n;i++)//前i行
for(ll j=0;j<=k;j++)//加上等会要放的，总计放了多少的棋
for(ll l=0;l<=num;l++)//二进制模拟
{
ll manynow=counts(l);//这一行放了多少个棋子
if(manynow>j)continue;//说明不包括这一行，前几行总共放了负数个棋子，显然不可能
if(illegal(l))continue;//对于这一行的棋子来说，最低要求是不能相邻
for(int u=0;u<=num;u++)//模拟上一行
{
if(check(u,l)||illegal(u))continue;//和上一行也不能在攻击范围内，攻击范围内不能有棋子，不代表攻击范围不能重合
dp[i][j][l]+=dp[i-1][j-manynow][u];
}
}
ll ans=0;
for(int i=0;i<=num;i++)
{
ans+=dp[n][k][i];//如果i不合法，那么dp~i一定为零，所以不用特判
}
printf("%lld\n",ans);
return 0;
}