威海医院网站制作/北京seo教师

题目链接【http://www.lydsy.com/JudgeOnline/problem.php?id=1087】

题意：在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。输入包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N），输出方案数。

解法：状压DP,首先处理每一行的有效状态，虽然有2^9种状态，但是同一行的有效状态不超过90，我们定义dp[i][t][x]表示：第i行的状态是x,并且一共用了t个国王的方案数。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[15][100][100];
LL sta[100], num[100], cnt;
int n, k;
void stacnt()
{int mask = (1 << n) - 1;for(int i = 0; i <= mask; i++){if((i & (i << 1)) || (i & (i >> 1))) continue;sta[++cnt] = i;int t = i;num[cnt] = __builtin_popcount(i);}
}
bool attrack(int x, int y)
{if(x & y) return false;if(x & (y << 1)) return false;if(x & (y >> 1)) return false;return true;
}
int main ()
{scanf("%d%d", &n, &k);stacnt();for(int i = 1; i <= cnt; i++)//预处理第一行的状态dp[1][num[i]][i] = 1;for(int i = 2; i <= n; i++)//第i层for(int t = 0; t <= k; t++)//一共用了多少个士兵for(int x = 1; x <= cnt; x++)//第i层的状态for(int y = 1; y <= cnt; y++)//第i-1层的状态
                {if(t - num[x] - num[y] >= 0 && attrack(sta[x], sta[y]))dp[i][t][x] += dp[i - 1][t - num[x]][y];}LL ans = 0;for(int i = 1; i <= cnt; i++)ans += dp[n][k][i];printf("%lld\n", ans);return 0;
}

转载于:https://www.cnblogs.com/pealicx/p/6423737.html