Oh，Oh勤劳的tc来了 。。
讲道理 很久没写了，也并不是很勤劳（小声bb）先是树形dp
就像他的名字这个dp是对像树一样的数据进行dp一般都是图，毕竟图你把每个点连起来就像树一样？！
说是dp其实我觉得像dfs+dp。
因为他的数据和树一样，所以普通的dp是完成不了的。首先他的一个节点上有很多个儿子结点，儿子节点上又有很多结点。所以这里用了dfs从他的叶子结点dp从他的叶子结点就开始判断最佳路径。
下面是题目
hdu 1011
首先他一个士兵可以打败20个怪兽意思，但是即使只有一个怪兽也要用1个士兵。所以这里判断士兵用量就是（bugs+19）/20 。然后dp的部分，先用一个数组二维的int型value[u][v]来记录他的路径。 u就是当前所在层数，然后v就是当前层数所有的士兵数，然后他是从后往前dp的所以他的dp转移方程就是
value[u][v]=max(value[u][v],value[u][v-j]+value[next][j]);这里的next就是和当前节点相连的一个节点然后他在第n层的最大brain获取量就是第u层留下v-j的brain获取量和next层花费j士兵是获取的brain量
code：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#define fastc cin.tie(NULL);
#define fasto cout.tie(NULL);
#define fasts ios::sync_with_stdio(false);
#define END return 0;
#include<iomanip>
using namespace std;
//char num[1000];
int value[101][101];//记录值进行dp
int visit[101];//看是否访问过，避免重复查找。
int rec[101][101];//记录地图
typedef pair<int,int> P;//储存bugs和brains
P pa[101];
int n,m;
void dp(int u) {
visit[u]=1;
int cost=(pa[u].first+19)/20;
for(int i=m; i>=cost; i--) {
value[u][i]=pa[u].second;//在第u层花费了cost个士兵都可以获得所有的brain
}
for(int i=1; i<=n; i++) {
if(rec[u][i] && !visit[i]) {
dp(i);
for(int j=m; j>=cost; j--) {
int rest=j-cost;
for(int k=1; k<=rest; k++) {
value[u][j]=max(value[u][j],value[i][k]+value[u][j-k]);
}
}
}
}
}
void prin() {
for(int i=0; i<=n; i++) {
for(int j=0; j<=m; j++) {
cout<<value[i][j]<<" ";
}
cout<<endl;
}
//cout<<endl;
}
int main() {
fastc fasto fasts
while(cin>>n>>m) {
if(n==m&&n==-1) break;
memset(value,0,sizeof(value));
memset(visit,0,sizeof(visit));
memset(pa,0,sizeof(pa));
memset(rec,0,sizeof(rec));
int i=1;
for(i; i<=n; i++) {
cin>>pa[i].first>>pa[i].second;
}
int one,two;
for(i=1; i<n; i++) {
cin>>one>>two;
rec[one][two]=1;
rec[two][one]=1;
}
dp(1);
prin();
cout<<value[1][m]<<endl;
}
END
}
题目：
dfs剪枝
hdu1010
这题是已经规定了步数
|0|1|0|1|0|1|
—|:—:|—:|—:|—:|—:|
|1|0|1|0|1|0|
|0|1|0|1|0|1|
|1|0|1|0|1|0|
|0|1|0|1|0|1|
|1|0|1|0|1|0|
|0|1|0|1|0|1|
|1|0|1|0|1|0|
|0|1|0|1|0|1|
|1|0|1|0|1|0|
|0|1|0|1|0|1|
可以知道从1走到0的步数一定是奇数
这里是最重要的一个剪枝，只有当起点的横纵坐标的奇偶性相同时，步数必须是奇数，反之则是偶数。
数论小知识
题目：
hdu1013
Digtial Roots=(sum-1)%9+1