最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

环球快消息!AcWing 1077. 皇宫看守

来源:博客园


(相关资料图)

解题思路

\(\qquad\) 题目就不再复述了,我们这题和上一题类似,可以采用树形DP+ 状态机

状态表示

\[f[i][j], j\in[0,2]表示的是第 i 个点,第 j 种状态\]

对于三种状态,有如下分类

\[f[i][0]表示的是不选当前节点,但是选择了父节点\]\[f[i][1]表示的是不选当前节点,但是选择了子节点\]\[f[i][2]表示的是选择当前节点\]

状态转移

\(\qquad\)首先看\(f[i][0]\),假设 \(j\) 是 \(i\) 的一个子节点,\(i\) 并没有选择,所以 \(f[j][0]\) 这个状态是无法转移到 \(f[i][0]\) 的(\(i\) 就是 \(j\) 的父亲, \(i\) 都不选自己,那就是不选 \(j\) 的父亲)。所以 \(j\) 只能自给自足或者选择自己的儿子,因此:

\[\large f[i][0] = \sum_{j\in son[i]} \min\{f[j][1], f[j][2]\}\]

\(\qquad\)接下来要考虑的是 \(f[i][1]\),因为这个状态需要整颗子树的信息,所以放到后面处理

\(\qquad\) 对于 \(f[i][2]\),因为 \(i\) 已经选择了自己,所以不管子节点怎么样,都是合法的,因此可以由子节点的三种状态转移而来

\[\large f[i][2] = \sum_{j\in son[i]} \min\{f[j][1], f[j][2], f[j][0]\}\]

\(\qquad\) 问题回到了 \(f[i][1]\)的身上,我们可以进行如下分析:\(\qquad\) 枚举 \(i\) 的所有子节点 \(j\),假设 \(j\) 是我们最终要选择的子节点,那么如果是选了这个儿子,其它儿子仍然是没有被父亲选的,所以其它儿子的代价也要加上,也就是总和去掉 \(f[j][2]\),因为前面有类似的情况 \(f[i][0]\) 已经保存了总和,那这里就不用另外处理了。

代码

#include #include #include using namespace std;const int N = 1510;int h[N], e[N], ne[N], w[N], idx;int st[N], root, n, f[N][3];void add(int a, int b) {    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}void dfs(int u) {    f[u][1] = 1e9, f[u][2] = w[u];    for (int i = h[u]; ~i; i = ne[i])     {        int j = e[i];        dfs(j);        f[u][0] += min(f[j][1], f[j][2]); //同时用作sum        f[u][2] += min({f[j][1], f[j][0], f[j][2]});    }    for (int i = h[u]; ~i; i = ne[i])     {        int j = e[i];        f[u][1] = min(f[u][1], f[u][0] + f[j][2] - min(f[j][1], f[j][2]));    }}int main() {    scanf("%d", &n);    memset(h, -1, sizeof h);    for (int i = 1; i <= n; i ++ )     {        int id, m, r, c;        scanf("%d%d%d", &id, &c, &m);        w[id] = c;        while (m -- )         {            scanf("%d", &r);            add(id, r);            st[r] = 1;        }    }    root = 1;    while (st[root]) root ++ ;    dfs(root);    printf("%d\n", min(f[root][1], f[root][2]));    return 0;}

关键词: 表示的是 因此可以 只能自给自足