点格棋

题目链接：LOJ 3378

题目大意

有一个 (n+1)*(m+1) 的格点组成的网格，然后两个人轮流操作，选两个相邻（距离为 1）且没有连边的点对连一个竖直或者水平的线段。
然后如果一个人连线之后一个新的位置的四个边界都有线段了，那这个人就获得一分，并要继续操作。
然后无法操作时结束，然后给你当前的局势，问你从现在开始算分，先手的分减去后手的分的最大值。
保证当前局势满足每个格子的四个边界都有 2 个或者 4 个线段。

思路

会发现每个格子看做点，那也就是说每个点要么没有边，要么有两条边。
那就是形成了一些环，以及单点。
那单点在之前就贡献了，所以完全不用管。

但是其实不是，它有边界，那边界就相当于一条边，所以会有环和链。

那不如先考虑只有链怎么做。
那会发现先手一定会给后手创造机会，那如果只有一个连通块，那后手就能把所有的都取完。
那如果不止一个连通块，后手选完这个连通块的所有点，就要变成了先手，再开一个连通块。

不过会发现这样无法解释第二个样例，因为其实你不一定要选完。
那怎么让自己停下来呢？就是要少贪点，比如对于链我们可以留下一个大小为 222 的，如果是环，那就至少要留下两个大小为 222 的（也就是要留 444 的大小）

那显然多留是不优的，你肯定是在你能拿且保住后手的基础上尽量多拿，否则如果不保后手为啥不全取完。
那考虑一些特别的情况，比如链长度为 222，环大小为 444。
发现如果链长度是 222，先手是可以不让后手保住后手的（就选中间的那个），但是环就没办法。

那我们就有状压 DP 是每个连通块是否处理，处理这些后手的最小费用（我用的是这个，也可以先手的最大费用）
那考虑优化，注意到对于所有的链，先手肯定会优先选长度最小的，因为先手是亏的。
那环也是这样。

那至少我们发现链，环，它们自己的顺序是固定的。
那就可以 fi,jf_{i,j}fi,j​ 来 DP，复杂度就是 O(n2∗n2)O(n^2*n^2)O(n2∗n2)（连通块数量是 n2n^2n2）

那 n=20n=20n=20 肯定能过。

代码

#include
#include
#includeusing namespace std;const int N = 24;
const int M = N * N;
int n, m, id[N][N], tot, fa[M], sz[M];
bool lr[N][N], ud[N][N], cir[M];
int a[M], b[M], f[M][M];int find(int now) {if (fa[now] == now) return now;return fa[now] = find(fa[now]);
}void add(int x, int y) {if (find(x) == find(y)) {cir[find(x)] = 1; return ;}sz[find(y)] += sz[find(x)]; fa[find(x)] = find(y);
}bool cmp(int x, int y) {return x > y;
}int main() {scanf("%d %d", &n, &m);for (int i = 0; i <= n; i++)for (int j = 1; j <= m; j++)scanf("%1d", &lr[i][j]);for (int i = 1; i <= n; i++)for (int j = 0; j <= m; j++)scanf("%1d", &ud[i][j]);for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {if (lr[i - 1][j] && lr[i][j] && ud[i][j - 1] && ud[i][j]) continue;id[i][j] = ++tot;}for (int i = 1; i <= tot; i++) fa[i] = i, sz[i] = 1;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {if (lr[i - 1][j] && lr[i][j] && ud[i][j - 1] && ud[i][j]) continue;if (i > 1 && !lr[i - 1][j]) add(id[i][j], id[i - 1][j]);if (j > 1 && !ud[i][j - 1]) add(id[i][j], id[i][j - 1]);}for (int i = 1; i <= tot; i++) if (fa[i] == i)if (cir[i]) b[++b[0]] = sz[i];else a[++a[0]] = sz[i];sort(a + 1, a + a[0] + 1, cmp);sort(b + 1, b + b[0] + 1, cmp);memset(f, 0x7f, sizeof(f));f[0][0] = 0;for (int i = 0; i <= a[0]; i++)for (int j = 0; j <= b[0]; j++) {if (i < a[0]) {int val = a[i + 1] - f[i][j];if (a[i + 1] > 2) val = max(val, (a[i + 1] - 2) - 2 + f[i][j]);f[i + 1][j] = min(f[i + 1][j], val);}if (j < b[0]) {int val = b[j + 1] - f[i][j];if (b[j + 1] >= 4) val = max(val, (b[j + 1] - 4) - 4 + f[i][j]);f[i][j + 1] = min(f[i][j + 1], val);}}printf("%d", -f[a[0]][b[0]]);return 0;
}