按照 250 -> 1000 -> 550… 的顺序开的题。。
结果 1000 没撸出来 250 又挂了果断爆了 0 。。（但是居然 Unrate 了我会乱说 .. ??。。）
。。。言归正传。。
Brief description:
550:
…
1000：
给定一颗树状迷宫，定义一次染色操作为：每次覆盖一格点，同时覆盖其上下左右四个方向所有可以延伸到的其它格点。
问至少进行多少次操作可完成染色。
（.. . N ≤ 50 .. ）
Analysis:
… 现场生算法：对每个转角位置建点，若两个转角位置通过路径相连则连边。。。
。。于是转化成一个变形的支配集问题。。（点集支配边集。。）。。
（于是这个方法还有待研究。。。）
第二种方法是对每条横竖边分离，根据转角位置连边。。转换成二分图边覆盖问题。。
。。但是有一些奇怪的树状数据这种方法会错。。。
。。。看来这种建模方法好像会丢拓扑信息。。（。。我试图贪心修正。。但看起来这种方法已经没救了。。）
。。于是对每个孤立的格点分别建点。。进行裸的动态规划。。
然后类比树的支配集问题，将状态分以下三类。。。
const int None = 0, Cover = 1, Extend = 2; // 还未被覆盖... 被覆盖但不可延伸 ... 被覆盖且可延伸...
之后枚举插头形状分情况讨论状态转移 或 做树上背包即可。。状态转移请看下图。。问号地区请自行脑补。。
-/0/1 ? 0 ? // None -/1 ? 1 ? // Cover 2 ? 2 ? // Extend x x 2 x // Guard
额。。下面以第三副图举例，要求正前方区域必须是 Extend，
同时左右两边要能安全覆盖，要不然是有一个 Extend，要不然是两面都是 Cover 。。。
具体书写的时候用 Delta 存一个差值。。和树的支配集的方法一样。。
另外值得注意的是，对于根结点需要默认一个正方向。
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const int N = 50, NN = N * N;
bool Grid[N][N]; int dp[3][N][N];
int n, m;
inline int _R(int d){
return d ^ 1;
}
inline int inGrid(int x, int y){
return x >= 0 && x < n && y >= 0 && y < m;
}
inline bool legal(int x, int y){
return inGrid(x, y) && Grid[x][y];
}
#define u0 dp[0][x][y]
#define u1 dp[1][x][y]
#define u2 dp[2][x][y]
#define v0 dp[0][xx][yy]
#define v1 dp[1][xx][yy]
#define v2 dp[2][xx][yy]
#define v12 min(v1, v2)
#define v012 min(v0, v12)
void dfs(int x, int y, int dir){
int c_ = 0, c0 = INF, c1 = INF, c2 = INF;
int s1 = 0, s12 = 0, s012 = 0, delta = INF, guard = 1;
bool leaf = true; REP(i, 4){
if (_R(i) == dir) continue;
int xx = x + dx[i], yy = y + dy[i];
if (legal(xx, yy)){
dfs(xx, yy, i); if (i == dir || dir == -1 && i <= 1) c_ = INF, c0 = v0, c1 = v1, c2 = v2;
else s1 += v1, s12 += v12, s012 += v012, checkMin(delta, v2 - v012);
guard += v012, leaf = false;
}
}
if (leaf) u0 = 0, u1 = INF, u2 = 1;
else {
s012 += delta, u0 = min(c_, c0, c1) + min(s1, s012), u1 = min(c_, c1) + s012;
u2 = min(c2 + min(s1, s012), guard);
}
}
class FoxBomb {
public:
int getMinimumCost(vector <string> grid){
n = SZ(grid), m = SZ(grid[0]); int x0 = -1, y0;
REP_2(i, j, n, m) Grid[i][j] = grid[i][j] == '.';
REP_2(x, y, n, m) if (Grid[x][y]) REP(d, 4){
int xx = x + dx[d], yy = y + dy[d];
if (legal(xx, yy)) x0 = xx, y0 = yy;
}
dfs(x0, y0, -1);
return min(dp[1][x0][y0], dp[2][x0][y0]);
}
};
