[洛谷2996] 拜访奶牛

link: P2996 [USACO10NOV]拜访奶牛Visiting Cows - 洛谷

非常简单的一道“树形DP”题。

首先要明确的是,这道题是无法用贪心实现的。下面是一个反例:

贪心反例

贪心的话最大值是5,然而可以在中途放弃一个点从而取到最大值6。

我们使用f[i][0]来表示到第i个点但不取这个点所能获得的最大值,用f[i][1]表示到第i个点且取这个点所能获得的最大值。

先将每个点都DFS遍历一遍,在回溯时进行DP(u是当前节点,G[u][i]是孩子节点):
f[u][0] += max(f[G[u][i]][0], f[G[u][i]][1]);(如果当前节点不选,那么孩子节点选或不选均可)
f[u][1] += f[G[u][i]][0];(如果当前节点选中,那么孩子节点只能不选)

代码

#include <bits/stdc++.h>
#define isnum(c) ('0' <= c && c <= '9')
#define read(x) do {\
    char c = getchar(); bool m = 0; x = 0;\
    while (!isnum(c) && c != '-') c = getchar();\
    if (c == '-') c = getchar(), m = 1;\
    while (isnum(c)) x = x * 10 + c - '0', c = getchar();\
    if (m) x = -x;\
} while(false) //宏定义快读
using namespace std;

const int maxn = 50010;
int n, tx, ty, a[maxn], tag[maxn], f[maxn][2];
vector < int > G[maxn];

void DFS(int u) {
    tag[u] = 1;
    f[u][1] = 1;
    for (int i = 0; i < G[u].size(); i++)
        if (!tag[G[u][i]]) {
            //没有打上tag标记说明是孩子节点
            DFS(G[u][i]);
            f[u][0] += max(f[G[u][i]][0], f[G[u][i]][1]);
            f[u][1] += f[G[u][i]][0];
        }
}

int main() {
    read(n);
    for (int i = 1; i < n; i++) {
        read(tx);
        read(ty);
        G[tx].push_back(ty);
        G[ty].push_back(tx);
    }

    DFS(1);
    printf("%d\n", max(f[1][0], f[1][1]));

    return 0;
} 
添加新评论

0%