下面这段代码求最大权独立集,但两个状态的注释被删掉了:
void dfs(int u) {
f[u][0] = 0; f[u][1] = w[u];
for (int v : ch[u]) {
f[u][0] += max(f[v][0], f[v][1]);
f[u][1] += f[v][0];
}
}
下面哪组注释是唯一与代码转移一致的?(注释对了,才说明状态真的想清楚了)
- A.
f[u][0]= 选、f[u][1]= 不选 - B.
f[u][0]= 不选、f[u][1]= 选 - C. 两个都表示「 选」
- D. 两个都表示「子树内选点个数」