文章目录
- 树形DP
- HDU-1520
- HDU-2196
树形DP
树形DP，顾名思义是在「树」这种数据结构上进行的DP，往往给定一棵树，通过指定操作求最小代价或最大收益等。
一般方向主要分①从子节点向根节点传递信息，②根节点向子节点传递
树操作一般利用递归和搜索，如树的遍历等，用dfs编程会比较简单，但往往状态转移方程不好设计，常常比较难(主要是我太菜了 )，令人头秃。做题步骤一般是：建树、树的遍历、DP。
HDU-1520
HDU-1520Anniversary party
Problem Description There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests’ conviviality ratings. Input Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go T lines that describe a supervisor relation tree. Each line of the tree specification has the form: 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 Output should contain the maximal sum of guests’ ratings. 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
#include<bits/stdc .h>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
const int maxn = 60005;
int n, x, y;
int v[maxn], dp[maxn][2], root[maxn];
vector<int>tree[maxn];
void dfs(int u) {
dp[u][0] = 0; //初始化不参加
dp[u][1] = v[u];//参加
for (int i = 0; i < tree[u].size(); i ) { //遍历其子节点
int son = tree[u][i];
dfs(son); //深搜子节点
dp[u][0] = max(dp[son][1], dp[son][0]);//父节点不选:取子节点选和不选最大值
dp[u][1] = dp[son][0];//父节点选:子节点不能选
}
}
int main() {
while (cin >> n) {
for (int i = 1; i <= n; i ) {
cin >> v[i];
root[i] = -1;
tree[i].clear();
}
while (cin >> x >> y) {
if (!x && !y)break;
root[x] = y; //父子关系
tree[y].push_back(x); //邻接表建树
}
int start = 1; //查根节点
while (root[start] != -1)
start = root[start];
dfs(start);
cout << max(dp[start][1], dp[start][0]) << "n";
}
return 0;
}HDU-2196
HDU-2196Computer
Problem Description A school bought the first computer some time ago(so this computer’s id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information. Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4. Input Input file contains multiple test cases.In each case there is natural number N (N<=10000) in the first line, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 10^9. Numbers in lines of input are separated by a space. Output For each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N). Sample Input 5 1 1 2 1 3 1 1 1 Sample Output 3 2 3 4 4
#include<bits/stdc .h>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
const int maxn = 10004;
struct node {
int id, cost;
node(int id, int cost) {
this->id = id;
this->cost = cost;
}
};
vector<node>tree[maxn];
int n, dp[maxn][3];
void init() {
for (int i = 1; i <= n; i )tree[i].clear();
memset(dp, 0, sizeof(dp));
int x, y;
for (int i = 2; i <= n; i ) {
cin >> x >> y;
tree[x].push_back({ i, y });
}
}
void dfs1(int father) { //先子结点再父结点
int l1 = 0, l2 = 0;
for (int i = 0; i < tree[father].size(); i ){ //遍历其子结点
node son = tree[father][i];
dfs1(son.id);
int cost = dp[son.id][0] son.cost;
if (cost >= l1) { //更新最长和次长
l2 = l1;
l1 = cost;
}
if (cost<l1 && cost>l2)l2 = cost;
}
dp[father][0] = l1;
dp[father][1] = l2;
}
void dfs2(int father) { //先父结点再子结点
for (int i = 0; i < tree[father].size(); i ) {
node son = tree[father][i];
if (dp[son.id][0] son.cost == dp[father][0]) //son在最长子树上
dp[son.id][2] = max(dp[father][2], dp[father][1]) son.cost;
else //不在最长子树上
dp[son.id][2] = max(dp[father][2], dp[father][0]) son.cost;
dfs2(son.id);
}
}
int main() {
while (cin >> n) {
init();//初始化
dfs1(1);//计算dp[][0]、dp[][1]
dp[1][2] = 0;//根结点往上走最长距离为0
dfs2(1);//计算dp[][2]
for (int i = 1; i <= n; i )
cout << max(dp[i][0], dp[i][2]) << "n";
}
return 0;
}原创不易，请支持正版。（百度发现我的好多博客被抄袭
qswl） 博主首页：https://blog.csdn.net/qq_45034708
