首页 > 其他分享 >树形dp

树形dp

时间:2023-02-11 16:46:41浏览次数:39  
标签:Hi idx int 树形 dp include 节点 职员

没有上司的舞会

Ural 大学有 N 名职员,编号为 1∼N 。
他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。
每个职员有一个快乐指数,用整数 Hi 给出,其中 1≤i≤N。
现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。
在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。

输入格式

第一行一个整数 N。
接下来 N 行,第 i 行表示 i 号职员的快乐指数 Hi。
接下来 N−1 行,每行输入一对整数 L,K,表示 K 是 L 的直接上司。

输出格式

输出最大的快乐指数。

数据范围

1≤N≤6000,
−128≤Hi≤127

输入样例:

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

输出样例:

5


代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 6010;
int n;
int happy[N]; //每个职工的高兴度
int f[N][2]; 
int e[N], ne[N], h[N], idx; //链表,用来模拟建一个树
bool has_father[N]; //判断当前节点是否有父节点
void add(int a, int b) { //把a插入树中
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u) { //开始求解题目
	f[u][1] = happy[u]; //如果选当前节点u,就可以把f[u,1]先加上他的高兴度
	for (int i = h[u]; ~i; i = ne[i]) { //遍历树
		int j = e[i];
		dfs(j); //回溯
		f[u][0] += max(f[j][1], f[j][0]);
		f[u][1] += f[j][0];
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) scanf("%d", &happy[i]); //输入每个人的高兴度
	memset(h, -1, sizeof h); //把h都赋值为-1
	for (int i = 1; i < n; i ++) {
		int a, b; //表示b是a的上司
		scanf("%d%d", &a, &b); //输入~
		has_father[a] = true; //说明a有上司
		add(b, a); //把a加入到b的后面
	}
	int root = 1; //用来找根节点
	while (has_father[root]) root ++; //找根节点
	dfs(root); //从根节点开始搜索
	printf("%d\n", max(f[root][0], f[root][1])); //输出不选根节点与选根节点的最大值
	return 0;
}

标签:Hi,idx,int,树形,dp,include,节点,职员
From: https://www.cnblogs.com/wustRen/p/17111953.html

相关文章

  • Python引入模块报错:Import "openai" could not be resolvedPylancereportMissingImpor
    复制Openai的代码进行测试的时候,发生:Import"openai"couldnotberesolvedPylancereportMissingImports  以为是安装问题,检查安装,发现没有这个模块: 直接进行......
  • 71udp,tcp
    udp相当与写信,tcp相当于打电话1、基于连接与无连接;2、对系统资源的要求(TCP较多,UDP少);3、UDP程序结构较简单;4、流模式与数据报模式;5、TCP保证数据正确性,UDP可能丢包;6......
  • 某种DP
    某种DP感觉没见到固定的专业术语,我习惯叫它为预设性\(DP\),也有人叫它连续段\(DP\),插入\(DP\)为什么这么说?因为\(DP\)的过程就是预先留出位置,然后把元素按照某种......
  • Docker搭建LNMP+wordpress
    一、项目模拟1.项目环境公司在实际的生产环境中,需要使用Docker技术在一台主机上创建LNMP服务并运行Wordpress网站平台。然后对此服务进行相关的性能调优和管理工......
  • dpkg apt-get apt 安装
    dpkg、apt-get、apt是debain系列版本安装软件的工具,Ubuntu是再debain基础上开发出来的apt-get是对dpkg的封装,apt是对apt-get的封装dpkg不会自动安装依赖包,apt、apt-get会......
  • LeetCode接雨水(/dp 单调栈 双指针)
    原题解题目给定n个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。约束题解解法一classSolution{public:inttra......
  • [蓝桥杯 2019 省 A] 组合数问题-Lucas定理、数位dp
    洛谷的题目链接:https://www.luogu.com.cn/problem/P8688Lucas定理,把\(k|binom{i}{j}\)转换成在k进制下存在某个数位i比j小,再转换成反面计算每一位i都比j大,然后就是经典......
  • [dp 记录] CF1152F2 Sonya and Informatics
    trick:从值域考虑。好题。但是感觉和CF1151F差不多难。两题都是*3000但是一紫一黑。题意:对长度为\(k\),值域\(n\)的序列计数:\(a_i\leqa_{i-1}+m\)\(\fora......
  • vue 前端, 树形菜单的回显
      //树菜单回显(多级)  changeDetSelect(key,treeData){   letarr=[];//在递归时操作的数组   letreturnArr=[];//存放结果的数组 ......
  • [dp 记录] CF1342F
    trick:dp数组定义域与值域的互换。基本复读魏老师题解。题意:将\(n\)数合并为\(m\)集合,每个集合取出一个代表元,使得(代表元下标,集合和)构成偏序关系。最大化\(m\)并......