[动态规划][树形dp]Anniversary party
2018-08-02 05:44:00来源:博客园 阅读 ()
Description
Input
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0
Output
Sample Input
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
Sample Output
5
思路:树形dp;定义状态dp[i][0]表示编号为i的员工不来时,以他为根的子树所能获得的最大rating和;dp[i][1]表示编号为i的员工来时,以他为根的子树所能获得的最大rating和;
状态转移方程为dp[i][0]=sum{max(dp[j][0],dp[j][1]),j为i的直接下属},dp[i][1]=rating[i]+sum{dp[j][0],j为i的直接下属};
AC代码:
#include <iostream> #include <cstdio> using namespace std; int dp[6010][2]; int fa[6010]; int n; void dfs(int root){ for(int i=1;i<=n;i++){ if(i==root) continue; if(fa[i]==root) { dfs(i); dp[root][1]+=dp[i][0]; dp[root][0]+=max(dp[i][1],dp[i][0]); } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) fa[i]=i,scanf("%d",&dp[i][1]); int x,y; while(scanf("%d%d",&x,&y)&&(x||y)) fa[x]=y; int root=1; while(fa[root]!=root) root=fa[root];//找到整棵树的根节点 dfs(root); printf("%d\n",max(dp[root][0],dp[root][1])); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- [题记-动态规划] 编辑距离 - leetcode 2020-04-06
- anniversary party_hdu1520 2020-02-16
- 动态规划:最大子串和 2020-01-30
- 关于 DP 的一些内容 2019-12-25
- C++动态规划实现查找最长公共子序列 2019-10-31
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash