POJ 1739 Tony's Tour——插头dp

POJ 1739 Tony's Tour——插头dp

#include #include #include #include using namespace std;const int maxn = 15;const int seed = 2e5 + 7;typedef long long ll;char ch;int n, m, a[maxn][maxn], bit[maxn*2];int pre, cur, total[2], state[2][seed];ll dp[2][seed], ans;int tot, head[seed];struct Edge { int to, next; } edges[seed];void init() { memset(a, 0, sizeof(a)); for (int i = 0; i < maxn*2; i++) bit[i] = i<<1; pre = -1, cur = 0; total[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; } } total[cur]++; edges[++tot].to = total[cur]; edges[tot].next = head[u]; head[u] = tot; state[cur][total[cur]] = s; dp[cur][total[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; total[cur] = 0; for (int k = 1; k <= total[pre]; k++) { int s = state[pre][k]; ll num = dp[pre][k]; int r = (s>>bit[j-1])%4; int d = (s>>bit[j])%4; if (!a[i][j]) { if (!r && !d) addedge(s, num); } else if (!r && !d) { if (a[i][j+1] && a[i+1][j]) addedge(s+(1<>bit[u])%4; if (v == 1) temp++; else if (v == 2) temp--; if (!temp) { addedge(s-(1<= 0; u--) { int v = (s>>bit[u])%4; if (v == 2) temp++; else if (v == 1) temp--; if (!temp) { addedge(s+(1<

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