经典状压DP.
f[i][j][k]=sum(f[i-1][j-cnt[k]][k]); cnt[i]放置情况为i时的国王数量
前I行放置情况为k时国王数量为J
#include <iostream>
#include <cstdio>
using namespace std;
#define N 1<<9
long long ans;
int n,m;
int ok_1[N],cnt[N];
int ok_2[N][N];
long long dp[][*+][N];
void init()
{
int sum;
for (int i=;i<(<<n);i++)
{
if ((i&(i<<))== && (i&(i>>))==)
{
sum=;
for (int j=i;j;j>>=) sum+=(j&);
cnt[i]=sum; ok_1[i]=;
}
for (int i=;i<(<<n);i++)
if (ok_1[i])
for (int j=;j<(<<n);j++)
if (ok_1[j])
if ((i&j)== && (i&(j>>))== && (i&(j<<))==)
ok_2[i][j]=;
}
}
int main()
{
scanf("%d%d",&n,&m);
init();
for (int i=;i<(<<n);i++) if (ok_1[i]) dp[][cnt[i]][i]=;
for (int i=;i<=n;i++)
for (int j=;j<(<<n);j++)
if (ok_1[j])
for (int k=;k<(<<n);k++)
if (ok_1[k])
if (ok_2[j][k])
for (int l=cnt[k];l+cnt[j]<=m;l++)
dp[i][l+cnt[j]][j]+=dp[i-][l][k];
for (int i=;i<(<<n);i++)
ans+=dp[n][m][i];
printf("%lld\n",ans);
return ;
}
Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
Sample Input
3 2
Sample Output
16