SRM 598 div1 hard: TPS
解法
頂点数が 1 の場合を除いて, とりあえず 1 つのビーコンを置く必要があります。最初にビーコンを置いた場所を root にした木で, あと最低いくつのビーコンを置かなければならないか, というように考えます。
ある頂点 v に num 個の子があったとすると, そのうち num-1 個の子より下のどこかに, ビーコンを置かなければならず, 逆に num-1 個のビーコンがあれば, v の下の子頂点はすべて区別出来るようになります(全体の木 - v から下の部分木の部分は, どのみち v より下の頂点では区別できない)。
そこで, dp[v][need] = (頂点 v 以下で, v 以下のどこかにビーコンを置く必要があるかのフラグが need であるような場合に, v より下に置かなければならないビーコンの最低数) とすると, 木 DP が出来ます。
int dp[55][2]; vector<vi> G; int dfs(int v, int p, int need) { int& ret = dp[v][need]; if (ret >= 0) return ret; vector<int> children; for (int el : G[v]) if (el != p) children.push_back(el); int num = children.size(); if (num == 0) { if (need) return ret = 1; else return ret = 0; } else if (num == 1) { return ret = dfs(children[0], v, need); } ret = G.size(); for (int i = 0; i < num; i++) { int tmp = 0; for (int j = 0; j < num; j++) { if (i==j) tmp += dfs(children[j], v, 0); else tmp += dfs(children[j], v, 1); } ret = min(ret, tmp); } return ret; } class TPS { public: int minimalBeacons(vector <string> linked) { int n = linked.size(); G.resize(n); for (int i = 0; i < n; i++) { G[i].clear(); for (int j = 0; j < n; j++) { if (linked[i][j] == 'Y') G[i].push_back(j); } } int ans = n-1; for (int root = 0; root < n; root++) { memset(dp, -1, sizeof(dp)); ans = min(ans, 1+dfs(root, -1, 0)); } return ans; }