链接:

https://www.acwing.com/problem/content/287/

题意:

Ural大学有N名职员，编号为1~N。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

思路:

考虑Dp[u][j], 记录以点u为根节点, 使用u和不使用u的最大值.

递归一遍, 递推即可.

u点使用, 则子节点不使用.

u点不使用, 则子节点可用可不用.

注意找到根节点.

代码:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e4+10;

int Dp[MAXN][2];

int a[MAXN], dis[MAXN];

vector<int> G[MAXN];

int n;

void Dfs(int u, int fa)

{

    int sum1 = 0, sum2 = 0;

    for (int i = 0;i < G[u].size();i++)

    {

        int node = G[u][i];

        if (node == fa)

            continue;

        Dfs(node, u);

        sum1 += Dp[node][1];

        sum2 += Dp[node][0];

    }

    Dp[u][1] = a[u]+sum2;

    Dp[u][0] = max(sum1, sum2);

}

int main()

{

    scanf("%d", &n);

    for (int i = 1;i <= n;i++)

        scanf("%d", &a[i]);

    int u, v;

    for (int i = 1;i <= n;i++)

    {

        scanf("%d%d", &u, &v);

        G[v].push_back(u);

        dis[u]++;

    }

    int p;

    for (int i = 1;i <= n;i++)

    {

        if (dis[i] == 0)

        {

            p = i;

            break;

        }

    }

    Dfs(p, 0);

    printf("%d\n", max(Dp[p][1], Dp[p][0]));

    return 0;

}

巴特西

Acwing-285-没有上司的舞会(树型DP)

链接:

题意:

思路:

代码:

最新文章

热门文章