首页 > 代码库 > _bzoj1087 [SCOI2005]互不侵犯King【dp】
_bzoj1087 [SCOI2005]互不侵犯King【dp】
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1087
令f(i, j, k)表示前i列,二进制状态为j,已经用了k个国王的方案数,则
f(i, j, k) = sigma(i - 1, p, k - num[j]),其中可以从p状态转化到j状态,num[j]表示j状态下的国王数。
乍一看可能会超时,因为共有n * 2^n * n^2个状态,即状态数为O(n^3 * 2^n),转移的复杂度为O(2^n),因此总时间复杂度为O(n^3 * 2^2n),严重超时,其实不然。首先很多状态本身就不合法,比如邻接着的两个国王,这就已经剔除很多状态了,然后能转移过来的状态就更少了,所以不会超时的。
#include <cstdio> #include <cstring> int n, kk, num[515], S[515]; long long f[11][515][85], ans; int head[515], next[512 * 512], to[512 * 512], lb; inline void ist(int aa, int ss) { to[lb] = ss; next[lb] = head[aa]; head[aa] = lb; ++lb; } int main(void) { memset(next, -1, sizeof next); memset(head, -1, sizeof head); scanf("%d%d", &n, &kk); for (int i = 0; i < (1 << n); ++i) { S[i] = (1 << n) - 1; for (int j = 0; j < n; ++j) { if (i >> j & 1) { ++num[i]; if (j) { if (i >> (j - 1) & 1) { num[i] = -1; break; } S[i] &= (~(1 << (j - 1))); } S[i] &= (~(1 << j)); if (j < n - 1) { S[i] &= (~(1 << (j + 1))); } } } } for (int i = 0; i < (1 << n); ++i) { if (num[i] == -1) { continue; } for (int j = 0; j < (1 << n); ++j) { if (num[j] != -1 && (S[i] | j) == S[i]) { ist(i, j); } } } f[0][0][0] = 1; for (int i = 1; i <= n; ++i) { for (int j = 0; j < (1 << n); ++j) { for (int k = num[j]; k <= kk; ++k) { for (int p = head[j]; p != -1; p = next[p]) { f[i][j][k] += f[i - 1][to[p]][k - num[j]]; } } } } for (int j = 0; j < (1 << n); ++j) { ans += f[n][j][kk]; } printf("%lld\n", ans); return 0; }
_bzoj1087 [SCOI2005]互不侵犯King【dp】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。