JHwong

用户名：dotcpp0724243

访问量：832

签　名：

等　　级
排　　名	3377
经　　验	1946
参赛次数	11
文章发表	16
年　　龄	0
在职情况	学生
学　　校	宁波大学科学技术学院
专　　业

　　自我简介：

TA的其他文章

蓝桥第7/8届练习题解
浏览：89

你可能喜欢

1319: 没有上司的晚会

　　作者: JHwong　　　　发表时间：2024-01-13 19:36:52 浏览：33　|　评论：0　

原题链接：没有上司的晚会

# 没有上司的晚会
```cpp
/* 
 * 1319: 没有上司的晚会
 * 贴脸的树形DP，hhh。已知关系结构是树形，数据范围 -- 考虑dp。
 * dp[root][join] = 表示root在join情况下的最大值。
 * dp[root][1] = sum(dp[sons][0]);
 * dp[root][0] = sum(max{dp[sons][0],dp[sons][1]})
 */
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#define MAX_N 6005
#define NO false
#define YES true
#define JOIN true

int happiness[MAX_N];
std::vector<int> subordinate[MAX_N];
int dp[MAX_N][2];
int is_no_master[MAX_N]; // 标记校长 -- 输入没有给出校长节点是那个

int dfs(int u, int join) {
  if (subordinate[u].size() == 0) return dp[u][join] = happiness[u] * join;
  if (dp[u][join]) return dp[u][join];

int res = 0;
  if (join) {
	for (int i = 0; i < subordinate[u].size(); ++i)
	  res += dfs(subordinate[u][i], !JOIN);
	res += happiness[u];
  }
  else for (int i = 0; i < subordinate[u].size(); ++i)
	  res += std::max(dfs(subordinate[u][i], JOIN), dfs(subordinate[u][i], !JOIN));
  return dp[u][join] = res;
}

int main() {
  int number_of_people;
  scanf("%d", &number_of_people);
  for (int i = 1; i <= number_of_people; ++i) scanf("%d", happiness + i);
  
  {
	int l, k;
	while (scanf("%d %d", &l, &k) && (l | k)) {
	  subordinate[k].push_back(l);
	  is_no_master[l] = YES;
	}
  }

for (int i = 1; i <= number_of_people; ++i) if (!is_no_master[i])
	printf("%d", std::max(dfs(i, JOIN), dfs(i, !JOIN)));
  return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JHwong

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C二级辅导-温度转换（C语言代码）

点我有惊喜！你懂得！

C二级辅导-同因查找（C语言代码）

川哥的吩咐（C语言代码）

1319: 没有上司的晚会

评论区

精彩推荐

时间转换（Java代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

WU-复数求和（C++代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

关于C语言变量位置的问题

图形输出（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

陶陶摘苹果2 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

JHwong

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C二级辅导-温度转换 （C语言代码）

点我有惊喜！你懂得！

C二级辅导-同因查找 （C语言代码）

川哥的吩咐 （C语言代码）

1319: 没有上司的晚会

评论区

精彩推荐

时间转换 （Java代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

WU-复数求和 （C++代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

关于C语言变量位置的问题

图形输出 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

陶陶摘苹果2 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C二级辅导-温度转换（C语言代码）

C二级辅导-同因查找（C语言代码）

川哥的吩咐（C语言代码）

　　评论区

时间转换（Java代码）

WU-复数求和（C++代码）

图形输出（C语言代码）