POJ 2342 链接 http://poj.org/problem?id=2342
树形 dp 入门题, 对于几乎没有接触树形 dp 的同学来说, 是不错的练习题.
题目大意:
一棵有向树中, 节点带权值 , 选择其中一些节点使得选择的总的节点权值最大, 选择的规则是不能同时选择一个节点和他的直接父亲节点.
解题思路:
无疑是一个多决策问题, 在多步决策中得到最优的答案. 考虑 dp, 树形结构, 树形 dp .
设计状态:
dp[i][0] 表示没有选择该节点的最大价值和
dp[i][1] 表示选择该节点的最大价值和 , 输入的时候就可以初始化
- dp[i][0]=sigma(max(dp[son][0] ,dp[son][1]))
- dp[i][1]=sigma(dp[son][0])
最后用 dfs 找每一个节点的孩子节点 .dfs 从根节点出发, 当地状态转移是从叶子节点开始的 . 这一点好好理解 .
代码
- //#include<bits/stdc++.h>
- #include<iostream>
- #include<algorithm>
- #include<stdio.h>
- #include<vector>
- using namespace std;
- const int N=6e3+10;
- int dp[N][2];
- int root[N];
- vector<int>ve[N];
- int n;
- int rt;
- void dfs(int u)
- {
- for(int i=0; i<ve[u].size(); i++)
- {
- int v=ve[u][i];
- dfs(v);
- dp[u][0]+=max(dp[v][0],dp[v][1]);
- dp[u][1]+=dp[v][0];
- }
- }
- int main()
- {
- scanf("%d", &n);
- for(int i = 1; i <= n; i++)
- scanf("%d", &dp[i][1]);
- int x, y;
- for(int i = 1; i < n; i++)
- {
- scanf("%d%d", &x, &y);
- ve[y].push_back(x);
- root[x] = 1; // 这里是找根节点
- }
- scanf("%d%d", &x, &y);
- for(int i=1; i<=n; i++)
- {
- if(root[i]!=1)
- {
- rt=i;
- break;
- }
- }
- dfs(rt);
- printf("%d",max(dp[rt][1],dp[rt][0]));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3038827.html