怎么写了一坨屎出来啊(恼)
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
using i64 = long long;
const int inf = 0x3f3f3f3f;
int p3[20], g[160];
vector<pair<int, int>> h[11][60000];
vector<int> state[11];
int n, m, k;
int id[11][60000], tot, f[2][2000];
int get(int x, int y) {
return (x % p3[y + 1]) / p3[y];
}
void set(int& x, int y, int z) {
x += p3[y] * (z - get(x, y));
}
bool check(int S) {
int last = -1, len = 0;
for (int j = 0; j < m; j++) {
int cur = get(S, j);
if (cur == last) {
len++;
} else {
if (last == 2 && len % 2) return false;
if (last == 1 && len < 2) return false;
len = 1;
}
last = cur;
}
if (last == 2 && len % 2) return false;
if (last == 1 && len < 2) return false;
return true;
}
bool check(int S, int i) {
for (int j = 0; j < m; j++)
if (get(S, j) && (g[i] >> j & 1))
return false;
return true;
}
int calc(int S, int T) {
int U = 0;
for (int j = 0; j < m; j++) {
int a = get(S, j), b = get(T, j);
if (a) {
if (b != a - 1) return -1;
} else {
set(U, j, b);
}
}
int last = -1, len = 0, res = 0;
for (int j = 0; j < m; j++) {
int cur = get(U, j);
if (cur == last) {
len++;
} else {
if (last == 1) {
if (len % 3) return -1;
res += len / 3;
} else if (last == 2) {
if (len % 2) return -1;
res += len / 2;
}
len = 1;
}
last = cur;
}
if (last == 1) {
if (len % 3) return -1;
res += len / 3;
} else if (last == 2) {
if (len % 2) return -1;
res += len / 2;
}
return res;
}
int main() {
p3[0] = 1;
for (int i = 1; i <= 11; i++) {
p3[i] = p3[i - 1] * 3;
}
int T;
cin >> T;
while (T--) {
cin >> n >> m >> k;
memset(g, 0, sizeof g);
while (k--) {
int x, y;
cin >> x >> y;
--y;
g[x] |= 1 << y;
}
if (state[m].empty()) {
state[m].clear();
for (int i = 0; i < p3[m]; i++) {
if (check(i)) {
state[m].emplace_back(i);
}
}
tot = 0;
for (auto S : state[m]) id[m][S] = ++tot;
for (auto a : state[m]) {
h[m][a].clear();
for (auto b : state[m]) {
int v = calc(a, b);
if (~v) {
h[m][a].emplace_back(b, v);
}
}
}
}
memset(f, -0x3f, sizeof f);
f[0][id[m][0]] = 0;
for (int i = 0; i < n; i++) {
int cur = i & 1, ne = (i + 1) & 1;
memset(f[ne], -0x3f, sizeof f[ne]);
for (auto a : state[m]) {
if (f[cur][id[m][a]] != -inf) {
for (auto [b, v] : h[m][a]) {
if (check(b, i + 1) && check(a, i + 1)) {
f[ne][id[m][b]] = max(f[ne][id[m][b]], f[cur][id[m][a]] + v);
}
}
}
}
}
cout << f[n & 1][id[m][0]] << '\n';
}
return 0;
}