1087: [SCOI2005]互不侵犯King
Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
Sample Input
3 2
Sample Output
16
题目类型：状压DP
算法分析：直接搜索由于数据规模比较大，会TLE~~。这里注意到每行之间存在一个递推的关系，考虑使用状压DP来求解。dp[i][j][k]表示前i行摆放k个国王且第i行的状态是j的方案数，这里j进行“状压”来表示状态。首先将不满足条件的状态都删去，只保留满足条件的(相邻格子之间没有1)。然后初始化第一行的状态(很重要的~~，不然算出来的结果都是0)，状态转移方程为：
dp[i][j][k] += Sigma (dp[i-1][q][k-cnt[j]]
其中q是能够转移到j的一个状态(合法的)，cnt[j]表示状态j所具有的国王数量，最后累加dp[n][所有合法的状态][m]的值即可，注意要使用long long！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 6; LL dp[16][666][100], sta[666][2]; LL n, m; LL PP (LL val) { LL res = 0; while (val > 0) { if ((val & 1) == 1) res++; val >>= 1; } return res; } int main() { // CFF; scanf ("%lld%lld", &n, &m); LL len = (1 << n) - 1, llen = 0; memset (dp, 0, sizeof (dp)); for (LL i = 0; i <= len; i++) if ((i & (i >> 1)) == 0) { LL tt = PP (i); if (tt <= m) { sta[llen][0] = i; sta[llen][1] = tt; llen++; } } for (LL i = 0; i < llen; i++) dp[1][sta[i][0]][sta[i][1]] = 1; for (LL i = 2; i <= n; i++) for (LL k = 0; k <= m; k++) for (LL j = 0; j < llen; j++) for (LL q = 0; q < llen; q++) if ((sta[j][0] & sta[q][0]) == 0 && ((sta[q][0] << 1) & sta[j][0]) == 0 && ((sta[q][0] >> 1) & sta[j][0]) == 0 && k >= sta[j][1]) dp[i][sta[j][0]][k] += dp[i-1][sta[q][0]][k-sta[j][1]]; LL res = 0; for (LL i = 0; i < llen; i++) res += dp[n][sta[i][0]][m]; printf ("%lld\n", res); return 0; } |
- « 上一篇：poj2385