当前位置: 首页 > news >正文

番禺网站建设培训班apt安装wordpress

番禺网站建设培训班,apt安装wordpress,什么网站程序可以做抽奖页面,苏州专业正规网站建设题目描述 某大学有 nnn 个职员,编号为 1…n1\ldots n1…n。 他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。 现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 ri…

题目描述

某大学有 nnn 个职员,编号为 1…n1\ldots n1n

他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。

现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 rir_iri

但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。

所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。

输入格式

输入的第一行是一个整数 nnn

222 到第 (n+1)(n + 1)(n+1) 行,每行一个整数,第 (i+1)(i+1)(i+1) 行的整数表示 iii 号职员的快乐指数 rir_iri

(n+2)(n + 2)(n+2) 到第 2n2n2n 行,每行输入一对整数 l,kl, kl,k,代表 kkklll 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

样例 #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^31n6×103−128≤ri≤127-128 \leq r_i\leq 127128ri1271≤l,k≤n1 \leq l, k \leq n1l,kn,且给出的关系一定是一棵树。

解题思路:

首先,注意题中说的是“如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。”

也就是说间接上司来不来是无所谓的

接下来讲解本题的解题思路

这道题可以算是树形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;
}
http://www.yayakq.cn/news/467889/

相关文章:

  • 深圳网站制作可选兴田德润wordpress自定后台
  • 上海市建设工程备案查询网站wordpress环境
  • 网站建设怎么放到云空间动态背景网站
  • 低价网站建设公司上海网站开发哪里好薇
  • 东莞市建设安监局网站首页企业建站电话多少
  • 自建网站好建吗开创云网站建设支持
  • 商务网站设计报告网站建设安全方案
  • 房产网站代理摄影招聘网站
  • 临淄网站建设价格短期职业技能培训班
  • 做餐饮加盟的网站建设聊城有限公司网站建设 中企动力济二分
  • 营销型企业网站建设的基本原则是珠海住建网站
  • 网站制作国内知名企业企业营销型网站seo推广
  • 网站开发外包公司有哪些部门普通的旧房装修价格
  • wordpress建站阿里云制作招聘海报的app
  • 人才招聘网站开发扬中网站推广哪家好
  • 松江手机网站建设彩票网站我想自己做
  • 孟村县做网站价格服装网站首页设计
  • 长春火车站最新通知网站上做的图片不清晰是怎么回事
  • 资源网站排名优化seo网站模板打包下载
  • 什么是网站主题优化汕头论坛贴吧
  • 5台电脑做视频网站服务器中国职业培训在线
  • 哪个网站的理财频道做的比较好wordpress虚拟目录图片打不开
  • html5手机网站制作网站编程用什么语言
  • 视频网站 阿里云网页拒绝了您的访问
  • 网站核心推广思路统计后台网站有哪些
  • 企业网站的种类想找人做网站
  • 深圳网站建设公司设计手机app网站模板下载
  • 北京品牌网站建设公司企业网站手机版
  • 网站建设程序源码电商网站建设渠道
  • 公司网站建设为什么不直接买模版什么叫专业建设