思路：将一颗大树分为若干子树，枚举每个子树
-
利用中序遍历
例如 P1040 [NOIP2003 提高组] 加分二叉树，利用中序遍历，所有的左儿子都在根节点的左边，所有的右儿子都在根节点的右边，且所有的子树在遍历中都是连续的。 因此可以枚举区间长度，再枚举起点和根节点。此外，应默认子树都没有左子树，否则一定不是最优解。
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
|
#include<iostream>
using namespace std;
long long dp[1001][1001], root[1001][1001];
void print(long long l, long long r)
{
if(l > r)
return;
cout << root[l][r] << " ";//print root
if(l == r)
return;
print(l, root[l][r] - 1);
print(root[l][r] + 1, r);
}
int main()
{
long long n;
cin >> n;
for (long long i = 1;i <= n;i++)
{
cin >> dp[i][i];
root[i][i] = i;
}
for(long long l = 1;l < n;l++)
{
for(long long i = 1;i + l <= n;i++)
{
long long j = i + l;
dp[i][j] = dp[i + 1][j] + dp[i][i];//right subtree
root[i][j] = i;
for(long long k = 1 + i;k < j;k++)
{
if(dp[i][j] < dp[i][k - 1] * dp[k + 1][j] + dp[k][k])
{
dp[i][j] = dp[i][k - 1] * dp[k + 1][j] + dp[k][k];
root[i][j] = k;
}
}
}
}
cout << dp[1][n] << endl;
print(1, n);
cout << endl;
return 0;
}
/*
f[i][j]来表示节点i到节点j最大值
*/
|
-
递归dfs
例子： P2015二叉苹果树 这道题需要用邻接表来存储每一条边。然后在dfs函数中只要一个节点有儿子（这条边所指向的点不是根节点），就以这个儿子为根节点再次进行dfs，并将其存储起来。因为每个节点都有且仅有两个分支，因此先遍历到的就是左儿子，后遍历到的是右儿子。
code:
1
2
3
4
5
6
7
8
9
10
|
for(int i = heads[x];i != 0;i = edge[i].next)
{
if(edge[i].to != fa)
{
doHaveSon = 1;
s[++cnt] = i;
dfs(edge[i].to, x);//subtree dfs
}
}
|
接下来进行dp， $dp[k，j]$表示以结点 $k$ 为父结点的子树中，保留j个树枝能留住的最多苹果数。所以转移方程为 $dp[i][j]=max(dp[i][j],dp[left][j−1]+edge[left].w+dp[right][k−j−1]+edge[right].w)$ (考虑left与i之间的树枝)
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
for(int i = 1;i <= q;i++)
{
for(int j = 0;j <= i;j++)
{
int tot = 0;
if(j - 1 >= 0)
tot += edge[s[1]].w;//lc
if(i - j - 1 >= 0)
tot += edge[s[2]].w;//rc
if(j != 0)
dp[x][i] = max(dp[x][i], dp[edge[s[1]].to][j-1] + tot + dp[edge[s[2]].to][i - j - 1]);
else
dp[x][i] = max(dp[x][i], dp[edge[s[2]].to][i - j - 1] + tot);
}
}
|
总的程序:
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
|
/*************************************************************************
> File Name: appletree.cpp
> Created Time: 09/03/21 - 15:45
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
struct EDGE{
int w, to, next;
}edge[1001];
int n, q, tot, dp[101][101], heads[101];
void add_edge(int from, int to, int w)
{
edge[++tot].next = heads[from];
edge[tot].w = w;
edge[tot].to = to;
heads[from] = tot;
}
void dfs(int x, int fa);
int main()
{
cin >> n >> q;
for(int i = 1;i < n;i++)
{
int a, b, c;
cin >> a >> b >> c;
add_edge(a, b, c);
add_edge(b, a, c);
}
dfs(1, 0);
cout << dp[1][q] << endl;
return 0;
}
void dfs(int x, int fa)
{
int s[3] = {0}, cnt = 0;//s[1] left s[2] right
bool doHaveSon = 0;
for(int i = heads[x];i != 0;i = edge[i].next)
{
if(edge[i].to != fa)
{
doHaveSon = 1;
s[++cnt] = i;
dfs(edge[i].to, x);//subtree dfs
}
}
if(!doHaveSon)
return;
for(int i = 1;i <= q;i++)
{
for(int j = 0;j <= i;j++)
{
int tot = 0;
if(j - 1 >= 0)
tot += edge[s[1]].w;//lc
if(i - j - 1 >= 0)
tot += edge[s[2]].w;//rc
if(j != 0)
dp[x][i] = max(dp[x][i], dp[edge[s[1]].to][j-1] + tot + dp[edge[s[2]].to][i - j - 1]);
else
dp[x][i] = max(dp[x][i], dp[edge[s[2]].to][i - j - 1] + tot);
}
}
}
|
-
树形背包DP
例子：P2014 选课
没啥好说的
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
|
/*************************************************************************
> File Name: choosecourse.cpp
> Created Time: 10/03/21 - 09:51
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
vector<int> E[101];
int dp[1001][1001], n, m, w[1001];//i as root choose j item
void dfs(int x)
{
for(int i : E[x])
{
dfs(i);
for(int j = m;j >= 0; j--)//总体积
{
for(int k = 0;k <= j; k++)//枚举子树的大小
{
dp[x][j] = max(dp[x][j], dp[x][j - k] + dp[i][k]);//i k子树选了k体积的价值 x j-k其他的选了剩下体积的价值
}
}
}
if(x)
{
for(int i = m;i > 0; i--)
{
dp[x][i] = dp[x][i - 1] + w[x];
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n; i++)
{
int fa;
cin >> fa >> w[i];
E[fa].push_back(i);
}
dfs(0);
cout << dp[0][m] << endl;
return 0;
}
|
一些有1点复杂的情况
例题：Vijos 1144 小胖守皇宫
HZOJ链接（反正Vijos在机房上不去：THIS
这道题分了三种情况，
在f数组中对应如下