文章目錄
- 樹形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