URAL 1519 Formula 1——插头dp

URAL 1519 Formula 1——插头dp

题意：

求一个棋盘的哈密顿回路个数

思路：

插头dp思路网上有很多就不啰嗦了，这里只说一下两行之间的状态转移，即由第i-1行最后一个格子推到第i行第一个格子。对于第i-1行最后一个格子，其转移完后得到的轮廓线由n个下插头和1个右插头组成，很明显这个右插头对第i行第一个格子没有影响，应该取消这个右插头；对于第i行第一个格子，其左面没有可以影响他的插头，应该是一个空状态。结合这两点，没转移完一行后我们都应该把当前所有状态*4

#include #include #include #include using namespace std;const int maxn = 15;const int seed = 5e5+7;typedef long long ll;//==========char ch;int n, m, ex, ey, a[maxn][maxn], bit[maxn*2];int pre, cur, cnt[2], state[2][seed];ll dp[2][seed], ans;int tot, head[seed];struct Edge { int to, next; } edges[seed];//==========void init() { ex = ey = -1; memset(a, 0, sizeof(a)); for (int i = 0; i < maxn*2; i++) bit[i] = i<<1; pre = -1, cur = 0; cnt[0] = 1; state[0][1] = 0; dp[0][1] = 1; ans = 0;}void addedge(int s, ll num) { int u = s % seed; for (int i = head[u]; ~i; i = edges[i].next) { int v = edges[i].to; if (state[cur][v] == s) { dp[cur][v] += num; return; } } cnt[cur]++; edges[++tot].to = cnt[cur]; edges[tot].next = head[u]; head[u] = tot; state[cur][cnt[cur]] = s; dp[cur][cnt[cur]] = num;}void plugdp() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { tot = 0; memset(head, -1, sizeof(head)); pre = cur; cur ^= 1; cnt[cur] = 0; for (int k = 1; k <= cnt[pre]; k++) { int s = state[pre][k]; ll num = dp[pre][k]; int is_right = (s>>bit[j-1])%4; int is_down = (s>>bit[j])%4; if (!a[i][j]) { if (!is_right && !is_down) addedge(s, num); } else if (!is_right && !is_down) { if (a[i][j+1] && a[i+1][j]) addedge(s+(1<>bit[u])%4; if (v == 1) temp++; if (v == 2) temp--; if (!temp) { addedge(s-(1<= 0; u--) { int v = (s>>bit[u])%4; if (v == 2) temp++; if (v == 1) temp--; if (!temp) { addedge(s+(1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。