网络教学网站建设,公司名称logo设计,医院做网站的意义,郑州企业网站制作公司题目描述
某大学有 nnn 个职员#xff0c;编号为 1…n1\ldots n1…n。
他们之间有从属关系#xff0c;也就是说他们的关系就像一棵以校长为根的树#xff0c;父结点就是子结点的直接上司。
现在有个周年庆宴会#xff0c;宴会每邀请来一个职员都会增加一定的快乐指数 ri…题目描述
某大学有 nnn 个职员编号为 1…n1\ldots n1…n。
他们之间有从属关系也就是说他们的关系就像一棵以校长为根的树父结点就是子结点的直接上司。
现在有个周年庆宴会宴会每邀请来一个职员都会增加一定的快乐指数 rir_iri
但是呢如果某个职员的直接上司来参加舞会了那么这个职员就无论如何也不肯来参加舞会了。
所以请你编程计算邀请哪些职员可以使快乐指数最大求最大的快乐指数。
输入格式
输入的第一行是一个整数 nnn。
第 222 到第 (n1)(n 1)(n1) 行每行一个整数第 (i1)(i1)(i1) 行的整数表示 iii 号职员的快乐指数 rir_iri。
第 (n2)(n 2)(n2) 到第 2n2n2n 行每行输入一对整数 l,kl, kl,k代表 kkk 是 lll 的直接上司。
输出格式
输出一行一个整数代表最大的快乐指数。
样例 #1
样例输入 #1
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5样例输出 #1
5提示
数据规模与约定
对于 100%100\%100% 的数据保证 1≤n≤6×1031\leq n \leq 6 \times 10^31≤n≤6×103−128≤ri≤127-128 \leq r_i\leq 127−128≤ri≤1271≤l,k≤n1 \leq l, k \leq n1≤l,k≤n且给出的关系一定是一棵树。
解题思路
首先注意题中说的是“如果某个职员的直接上司来参加舞会了那么这个职员就无论如何也不肯来参加舞会了。”
也就是说间接上司来不来是无所谓的
接下来讲解本题的解题思路
这道题可以算是树形DP的入门级题目了
树形DP就是在树形结构中采用动态规划 说了但好像什么都没说
常规思路就是自顶向下递推确定叶子节点后逐级回归更新父节点
那么这道题为什么采用树形DP呢
首先题目中给出的是一棵树
其次我们想要知道舞会的最大快乐指数除了遍历每一种可能外好像别无选择
那么降低时间复杂度就要想到DP在本题中也就是树形DP
思路很简单每个职员只有两种状态来、不来
我们用dp[now][1]表示来dp[now][0]表示不来
那么有
//树形DP
void dfs(int now) {//参加dp[now][1] happy[now];//参加初始化为自己的快乐指数//不参加for (int i head[now]; i ! -1; i edges[i].next) {//遍历子节点int v edges[i].v;dfs(v);//返回后更新dp[now][0] max(dp[v][0], dp[v][1]);//不参加需要累加子节点来的情况dp[now][1] dp[v][0];//参加需要累加子节点不来的情况}
}最后AC代码如下
#include iostream
#include string.h
using namespace std;
const int max_n 6e3;
const int min_r -128;
const int max_r 127;int n, u, v;
int happy[max_n 1];
int in[max_n 1];
//链式前向星
struct edge { int v, next; }edges[max_n 1];
int head[max_n 1];
int tot -1;
//树形DP
long long dp[max_n 1][2];//存边
void add_edge(int u, int v) {edges[tot] { v,head[u] }; head[u] tot;
}//树形DP
void dfs(int now) {//参加dp[now][1] happy[now];//参加初始化为自己的快乐指数//不参加for (int i head[now]; i ! -1; i edges[i].next) {//遍历子节点int v edges[i].v;dfs(v);//返回后更新dp[now][0] max(dp[v][0], dp[v][1]);//不参加需要累加子节点来的情况dp[now][1] dp[v][0];//参加需要累加子节点不来的情况}
}int main() {memset(head 1, -1, sizeof(int) * max_n);cin n;for (int i 1; i n; i) cin happy[i];for (int i 1; i n; i) {//存图cin u v;add_edge(v, u);//反向存边自顶向下in[u];}for (int i 1; i n; i)if (!in[i]) {//从根节点开始dfs(i);cout max(dp[i][0], dp[i][1]) endl;break;}return 0;
}
