连通性涂色插头$DP$板子题
默认第一格是黑色,每个状态需要记录轮廓线连通性、颜色、是否已加入过白色块,白色连通块是否贴边。
先睡了明天写。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5000, M = 10007;
const int offset = 3, mask = 7;
int a[8], num[8];
int n, m, all;
struct Hash_Table {
int h[M], ne[N], idx;
int state[N], col[N], val[N];
int flag[N], white[N];
void init() {
idx = 0, memset(h, -1, sizeof h);
}
void push(int s, int c, int f, int w, int v) {
int x = s % M;
for (int i = h[x]; ~i; i = ne[i])
if (state[i] == s && col[i] == c && flag[i] == f && white[i] == w)
return val[i] += v, void();
state[idx] = s, val[idx] = v, col[idx] = c;
flag[idx] = f, white[idx] = w;
ne[idx] = h[x], h[x] = idx++;
}
} h[2], *h0, *h1;
void add(int s, int c, int f, int w, int v) {
h1->push(s, c, f, w, v);
}
void decode(int s) {
for (int i = 0; i < m; i++)
a[i] = s & mask, s >>= offset;
}
int encode() {
memset(num, -1, sizeof num);
int k = -1, s = 0;
for (int i = m - 1; ~i; i--) {
if (!~num[a[i]])
num[a[i]] = ++k;
s = (s << offset) | num[a[i]];
}
return s;
}
void change(int x, int y) {
for (int i = 0; i < m; i++)
if (a[i] == x)
a[i] = y;
}
bool bound(int i, int j) {
return i == 0 || j == 0 || i == n - 1 || j == m - 1;
}
void trans(int i, int j, int c) {
for (int k = 0; k < h0->idx; k++) {
int s = h0->state[k], cc = h0->col[k], v = h0->val[k];
int f = h0->flag[k], w = h0->white[k];
int l = j ? (cc >> (j - 1) & 1) == c : 0;
int u = i ? (cc >> j & 1) == c : 0;
decode(s);
if (!cc && c && (i | j)) continue;
if (cc == all && !c && w) continue;
if (i > 0 && !u) {
int x = 0, y = 0;
for (int k = 0; k < m; k++) {
if (a[k] == a[j]) x++;
if ((cc >> k & 1) != c) y++;
}
if (x == 1 && y > 1) continue;
}
if (l && u) change(a[j], a[j - 1]);
else if (l && !u) a[j] = a[j - 1];
else if (!l && !u) a[j] = mask;
if (c) cc |= 1 << j;
else cc &= ~(1 << j);
int ns = encode(), nf = f | (!c & bound(i, j)), nw = w | !c;
add(ns, cc, nf, nw, v);
}
}
int main() {
cin >> n >> m;
all = (1 << m) - 1;
h0 = h, h1 = h + 1;
h1->init();
add(0, 0, 0, 0, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
swap(h0, h1);
h1->init();
if (i || j) trans(i, j, 0);
trans(i, j, 1);
}
}
int res = 0;
for (int i = 0; i < h1->idx; i++) {
int f = h1->flag[i], s = h1->state[i], cnt = 0;
decode(s);
for (int j = 0; j < m; j++)
cnt = max(cnt, a[j]);
if (f && cnt <= 1) res += h1->val[i];
}
cout << res;
return 0;
}