首页 > 其他分享 >P1352 没有上司的舞会

P1352 没有上司的舞会

时间:2024-05-10 17:25:32浏览次数:21  
标签:舞会 上司 int dfs fa P1352 include dp

链接:https://www.luogu.com.cn/problem/P1352


树形dp板子,感觉很巧妙,利用01表示是否取
代码:

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<cmath>
#include<limits.h>
#include<climits>
#include<fstream>
#include<set>
typedef long long ll;
using namespace std;
const int N = 1e4;
int val[N];
vector<int>G[N];
int fa[N], dp[N][2];
void dfs(int u)
{
	dp[u][0] = 0;
	dp[u][1] = val[u];
	for (int i = 0; i < G[u].size(); i++)
	{
		int v = G[u][i];
		dfs(v);
		dp[u][1] += dp[v][0];
		dp[u][0] += max(dp[v][0], dp[v][1]);
	}
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)cin >> val[i];
	for (int i = 1; i < n; i++)
	{
		int u, v; cin >> u >> v;
		G[v].push_back(u);
		fa[u] = v;
	}
	int t = 1;
	while (fa[t])t = fa[t];
	dfs(t);
	cout << max(dp[t][0], dp[t][1]);
	return 0;
}

标签:舞会,上司,int,dfs,fa,P1352,include,dp
From: https://www.cnblogs.com/zzzsacmblog/p/18184897

相关文章

  • 树形DP->没有上司的舞会(洛谷1352)
    题意:每个人有一个happ值,n个人,n-1条有向边,u是v的上司,求happy值最大。限制条件是u和v不能同时参加。分析:没想到一个v居然有很多上司,更没想到n-1条边居然是个森林。//没想到,一个员工居然可以有那么多上司。。voidsolve(){intn;cin>>n;vector<int>happy(n......
  • 【题解 P4062 & P8313】 Yazid 的新生舞会&Izbori
    [COCI2021-2022#4]Izbori题目描述Malnar先生正在竞选县长,这个县一共有\(n\)栋房屋,每栋房屋里都住着一位居民。Malnar先生知道,选举的赢家不一定是最好的候选人,而是在选举前举办的宴会最好的候选人。因此,在选举前几天,他将邀请第\(l\)至\(r(l\ler)\)栋房屋内居住的居民,为......
  • P4062 [Code+#1] Yazid 的新生舞会
    题外话我记得第一次看见这道题是几个月前刚开始集训的时候,当时一点思路都没有,但是今天自己做出来了,很喜欢这种感觉!\(\text{Links}\)原题传送门可能更好的阅读体验题意求给定序列中有多少个子区间满足众数出现次数严格大于区间长度的一半。题解题目要求满足条件的子区间......
  • P1352 没有上司的舞会
    考察算法:树形\(DP\)。题目概述给你一个树,每个结点有一个“上司”。每个节点都有一个快乐指数\(h_i\)。但是,如果有某个节点的上司(父亲),已经来到了舞会,那么它的儿子就不能去了。求:最大的快乐指数(所有人的快乐指数之和)。思路树形\(DP\)。设\(f_{i,0}\)表示以\(i\)作为......
  • Luogu P1352没有上司的舞会
    分析树形dp。定义状态\(dp_{~i,~0}\)为在以\(i\)为根节点的子树中,不选第\(i\)个人的最大快乐值,\(dp_{~i,~1}\)为在以\(i\)为根节点的子树中,选第\(i\)个人的最大快乐值。寻找根节点,然后从根节点开始dfs,当前节点\(u\)的\(dp\)初始状态为\(dp_{~i,~0}=0,~dp_{~i......
  • 题解 P1538 【迎春舞会之数字舞蹈】
    postedon2021-06-0113:24:05|under题解|source给\(0\cdots9\)每个数字打表,打它在相应的位置有没有一划。然后把每个数字分成\(5\)部分,暴力输出即可。#include<cstdio>#include<cstring>usingnamespacestd;constchar*db[]={"-||||-","||"......
  • 没有上司的舞会 - 树形动态规划
    没有上司的舞会-树形动态规划题意某大学有\(n\)个职员,编号为\(1\ldotsn\)。他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数\(r_i\),但是呢,如果某个职员的直接......
  • 1538 迎春舞会之数字舞蹈 题解
    #include<iostream>intmain(){/**#Seven-segmentDisplay**Thewayhowtheprogramprintsdecimalnumericstotheconsoleworks......
  • P1352 没有上司的舞会+P1122 最大子树和(树形DP入门)
    前言今日偶然打开\(oi-wiki\),发现树形\(DP\)例题正好是之前在洛谷上鸽着的一道题。所以......\(\color{red}{很高兴以这样的方式认识你,树形DP!}\)这例题造的太好了......
  • 我与外企上司的四个职场故事
    标题:我与外企上司的四个职场故事我在目前这家任职的外企从事软件开发工作,已经整整十五年了。本系列文章通过介绍我与自己上司的四个职场小故事,想和大家分享在外企里,一个程......