插头DP模板

it2022-05-06  9

/* 插头dp模板 抄的GNAQ 的 括号表示法 */ #include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<queue> #include<cmath> #define ll long long #define M 13 #define mmp make_pair using namespace std; int read() { int nm = 0, f = 1; char c = getchar(); for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0'; return nm * f; } const int hs = 299987; int mp[M][M], ex, ey, now, last, bit[30], g[2][300010], tot[2], n, m; ll ans, f[2][300010]; struct Note { int nxt, to; } note[300010]; int head[300010], cnt = 0; char s[M]; void insert(int x, ll v) { int key = x % hs; for(int i = head[key]; i; i = note[i].nxt) { if(g[now][note[i].to] == x) { f[now][note[i].to] += v; return; } } tot[now]++; g[now][tot[now]] = x; f[now][tot[now]] = v; note[++cnt].nxt = head[key]; head[key] = cnt; note[cnt].to = tot[now]; } void Dp() { now = 1, last = 0; tot[now] = 1; f[now][1] = 1; g[now][1] = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= tot[now]; j++) g[now][j] <<= 2; for(int j = 1; j <= m; j++) { cnt = 0; memset(head, 0, sizeof(head)); swap(now, last); tot[now] = 0; ll nowans; int nowsta, sd, sr; for(int k = 1; k <= tot[last]; k++) { nowsta = g[last][k], nowans = f[last][k]; sd = (nowsta >> bit[j]) % 4, sr = (nowsta >> bit[j - 1]) % 4; if(!mp[i][j]) { if(!sd && !sr) insert(nowsta, nowans); } else if(!sd && !sr) { if(mp[i + 1][j] && mp[i][j + 1]) insert(nowsta + (1 << bit[j - 1]) + 2 * (1 << bit[j]), nowans); } else if(!sd && sr) { if(mp[i + 1][j]) insert(nowsta, nowans); if(mp[i][j + 1]) insert(nowsta - sr * (1 << bit[j - 1]) + sr * (1 << bit[j]), nowans); } else if(sd && !sr) { if(mp[i + 1][j]) insert(nowsta - sd * (1 << bit[j]) + sd * (1 << bit[j - 1]), nowans); if(mp[i][j + 1]) insert(nowsta, nowans); } else if(sd == 1 && sr == 1) { int count = 1; for(int l = j + 1; l <= m; l++) { if((nowsta >> bit[l]) % 4 == 1) count++; else if((nowsta >> bit[l]) % 4 == 2) count--; if(!count) { insert(nowsta - (1 << bit[l]) - (1 << bit[j]) - (1 << bit[j - 1]), nowans); break; } } } else if(sd == 2 && sr == 2) { int count = 1; for(int l = j - 2; l >= 0; l--) { if((nowsta >> bit[l]) % 4 == 1) count--; else if((nowsta >> bit[l]) % 4 == 2) count++; if(!count) { insert(nowsta - 2 * (1 << bit[j]) - 2 * (1 << bit[j - 1]) + (1 << bit[l]), nowans); break; } } } else if(sd == 1 && sr == 2) { insert(nowsta - 2 * (1 << bit[j - 1]) - (1 << bit[j]), nowans); } else if(sd == 2 && sr == 1) { if(i == ex && j == ey) ans += nowans; } } } } } int main() { n = read(), m = read(); for(int i = 1; i <= n; i++) { scanf("%s", s + 1); for(int j = 1; j <= m; j++) { if(s[j] == '.') mp[i][j] = 1, ex = i, ey = j; } } for(int i = 1; i <= 25; i++) bit[i] = i << 1; Dp(); cout << ans << '\n'; return 0; }

转载于:https://www.cnblogs.com/luoyibujue/p/10515029.html

相关资源:插头DP模板待完成.md

最新回复(0)