解题思路:
这是一道树形DP,可以用深搜和动规来实现
定义dp数组:
int dp[10010][3];//dp[x][0]代表x没来快乐最大值,dp[x][1]代表x来了快乐最大值
定义一个二维数组,储存一个节点的下属
vector g[10010];
深搜主体代码:
void dfs(int x) //当前节点 { dp[x][0] = 0; dp[x][1] = v[x];//初始化 for(int i = 0; i < g[x].size(); i++) { dfs(g[x][i]);//先深搜!!搜索完才可以有数据来递推 dp[x][0] += max(dp[g[x][i]][0],dp[g[x][i]][1]);//上司没来取最大值 dp[x][1] += dp[g[x][i]][0];//上司来了下属只能不来 } }
还有一个问题,从哪里开始搜索?得找到根节点
根节点没有父节点
用b数组来存储x是否有父节点
int v[10010];
在输入过程中,顺便标记b数组
输入结束后,再遍历找出根节点root
void find_root() { for(int i = 1; i <= n; i++) if(b[i] == false) { root = i; break; } }
最后输出root节点的最大值
cout << max(dp[root][0],dp[root][1]) << endl;
参考代码:
#include <bits/stdc++.h> using namespace std; int dp[10010][3]; int v[10010]; vector g[10010]; bool b[10010]; int n,root; void read() { memset(b,false,sizeof(b)); cin >> n; for(int i = 1; i > v[i]; int x,y; while(1) { cin >> x >> y; if(!x && !y) break; g[y].push_back(x); b[x] = true; } } void find_root() { for(int i = 1; i <= n; i++) if(b[i] == false) { root = i; break; } } void dfs(int x) { dp[x][0] = 0; dp[x][1] = v[x]; for(int i = 0; i < g[x].size(); i++) { dfs(g[x][i]); dp[x][0] += max(dp[g[x][i]][0],dp[g[x][i]][1]); dp[x][1] += dp[g[x][i]][0]; } } int main() { read(); find_root(); dfs(root); cout << max(dp[root][0],dp[root][1]) << endl; return 0; }
0.0分
1 人评分
C语言训练-排序问题<1> (C语言代码)浏览:601 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:540 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:938 |
文科生的悲哀 (C语言代码)浏览:1401 |
小九九 (C语言描述,不看要求真坑爹)浏览:985 |
The 3n + 1 problem (C语言代码)浏览:505 |
勾股数 (C语言代码)浏览:800 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:673 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:624 |
检查金币 (C语言代码)浏览:1416 |