刷好题，固基础-2

本文主要是介绍刷好题，固基础-2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

7-5 运动会

T公司的员工层级关系可以表示成一棵树，员工X是员工Y的直接领导，则在树中X是Y的父结点。公司拟组织一场运动会，但为了避免尴尬，每个员工都不想与自己的直接领导一起参赛。假定每个员工都对应一个权重（领导的权重不一定比下属大），请你编写程序，邀请若干员工参赛，使得参赛人员的总权重和最大。

输入格式:

第一行一个正整数n，表示公司的员工人数，员工编号为1...n，n不超过3000。
接下来n行，每行1个整数，表示每个员工的权重，值域为[−27,27)。
接下来n-1行，每行为两个空格间隔的整数X和Y，表示Y是X的直接领导。

输出格式:

输出为一个整数，表示参赛员工的最大权重之和。

输入样例:

7
2
2
2
2
2
2
2
2 1
3 1
4 2
5 2
6 3
7 3

输出样例:

10

AC代码--动态规划 

#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
vector<int> v[N];
int dp_no[N];
int dp_join[N];
int n, root = 1, vi[N], w[N];void solve(int root){if(v[root].size() == 0){dp_join[root] = w[root];dp_no[root] = 0;return ;}dp_join[root] = w[root];for(int i = 0; i < v[root].size(); ++i){solve(v[root][i]);//如果当前节点被选，则需要w[当前节点] + 不被选的所有节点的值dp_join[root] += dp_no[v[root][i]];//如果当前节点未被选，则加上子节点被选or未被选的最大值（确保值最大化）dp_no[root] += max(dp_no[v[root][i]], dp_join[v[root][i]]);}/*因为当前结点的状态由它的子节点的状态推导而来，所以需要先dfs当前结点的子结点把它的子节点的两种状态计算出来，再回溯回来更新当前结点的两种状态当它的所有子节点的两种状态全部考虑完毕，当前结点的两种状态也随之确定*///当前结点的状态一dp_join[root]=wi[root]+每个子结点的状态二dp_no[wi[v[root][i]]]//上面这句话说明如果选了当前结点，那么它的子节点全部不能选，那只能选择子节点没有选的状态相加//当前结点的状态二dp_no[root]=每个子结点的状态一/状态二的最大值//上面这句话说明如果没选当前结点，那么它的子节点全部能选能不选，那选择子节点两种状态的较大者相加
}int main(){cin >> n;for(int i = 1; i <= n; ++i)    cin >> w[i];for(int i = 1; i < n; ++i){int x, y;    cin >> x >> y;v[y].push_back(x);vi[x] = 1;}for(int i = 1;i <= n; ++i)    if(vi[i] == 0){root = i; break;}solve(root);cout << max(dp_join[root], dp_no[root]);return 0;
}

 

这篇关于刷好题，固基础-2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---