按照 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]);
	}
};

Posted by xiaodao
Category: TopCoder
Tags: 支配集