0%

7.23夏令营总结

今天,我们主要学习了有关树状动态规划的初步学习。这是一种典型的DP,也是一种常用的DP。

树状动态规划:

所谓树状动态规划,就是一种动态规划,是建立在树的动态规划。通常是给一棵树,要求以最少的代价(或取得最大收益)完成给定的操作。(资料)

其实,通常来说,树形动态规划与区间动态规划有类似的地方。区间DP时,当每几个区间进行合并时,建立起之间的关系图时,这就是一棵树。

树形动态规划,与其他动态规划,一样,无非也就一下几点:

  1. 确立状态:几乎所以的问题都要保存以某结点为根的子树的情况,但是要根据具体问题考虑是否要加维,加几维,如何加维。

  2. 状态转移:状态转移的变化比较多,要根据具体问题具体分析,这也是本文例题分析的重点。

  3. 算法实现:由于树的结构,使用记忆化搜索比较容易实现。

例题1:二叉苹果树

【题目】给定一棵二叉树(只分二叉),每条枝干之间有苹果,要求去掉一些枝干,只留下K条枝干,问最多可以留下几个苹果?

【输入】

5 2

1 3 1

1 4 10

2 3 20

3 5 20

【输出】

21

他不见了。

【分析】首先,我们寻找突破口。如果用贪心,但我们却找不到一种恰当的方法。用搜索,当然可以。

首先,我们要找到子问题,搜索才可以进行下去,

他不见了。

以1为根结点需要留下K条枝干,那么它的子问题就是它左右两个子树,以2为根结点的树,以及以3为根结点的树。

那么,我们枚举左右两颗子树分别需要留下多少枝干。

① 若左子树留下0条枝干(默认砍掉节点1和2之间的枝干,也就是整个左子树砍掉),右子树留下K条枝干,那么子问题就是,右子树留下K-1条枝干的子问题。至于K要减1,是因为节点1和3之间的枝干,已经留下了,故要减1。

② 若左子树留下1条枝干,右子树留下K-1条枝干,那么子问题就是,左子树留下1-1=0条枝干,右子树留下K-1-1=K-2条枝干。因为节点1和2,节点1和3,之间的枝干,已经默认这两条枝干留下了。

③ 若左子树留下i条枝干,右子树留下K-i条枝干,那么子问题就是,左子树留下i-1条枝干,右子树留下K-i-1条枝干。

④ 若左子树留下K条枝干,右子树留下0条枝干(默认砍掉节点1和3之间的枝干,也就是整个右子树砍掉),那么子问题就是,左子树留下K-1条枝干的子问题。

⑤ 依此类推。

左右两个子树运行回来的结果,加上节点1和2之间的枝干的苹果树(i!=0),以及节点1和3之间的枝干的苹果树(i!=K),枚举每一次的最大值,就是结果。

如果运行到了叶节点,怎么办呢?没关系。我们知道,叶节点,一定是没有孩子的。首先我们判断当前节点有没有孩子,没有的话,当前节点就是叶节点。而叶节点是没有孩子与之相连的,因此,以叶节点为根的树,只能留下0条枝干。若K!=0,返回负无穷即可。

【注意点】

首先就是树的存储。我们没有学习链表,但vector是一个不错的选择。vector[i]表示以i为父节点,与i相连的节点(包括父节点)。读入时,若为a连上b,不仅要vector[a].push_back(b)还vector [b].push_back(a)。

然后就是边的权值的储存。vector[i]=[j1,jk,jm],表示i点与j1点,jk点,jm点相连,那么我们用vector类型的w[i]=[c1,ck,cm],表示i与j1相连时的权值是c1,i与jk相连时的权值是ck,i与jm相连时的权值是cm。j与c是位置是一一对应的。

dfs时,假如i点与j点之间的连线权值是c(i是根结点),那么,我们可以将c储存在节点j中(另开数组),这样,就可以很好地表示权值了。

最后就是dfs时的记忆化。具体的就不说了,只需,储存当前节点,留下K条枝干,可留下最多苹果的值即可。

【程序】

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
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("binary_apple_tree.in");
ofstream fout("binary_apple_tree.out");

#define maxn 1000+10
#define oo 100000000

vector <int> adj[maxn];
vector <int> w[maxn];
int F[maxn][102];
int cost[maxn];
int N,K;

void in_() {
fin >> N >> K;
for (int i=0; i!=N; ++i) {
int a ,b ,c;
fin >> a >> b >> c;

adj[a].push_back(b);
adj[b].push_back(a);
w[a].push_back(c);
w[b].push_back(c);
}

for (int i=0; i<=maxn; ++i)
for (int j=0; j<=102; ++j)
F[i][j]=-oo;
}



int dfs(int fa, int root, int k) {
int son[2],s=0;

for (int i=0; i!=adj[root].size(); ++i)//找当前节点的孩子
if (adj[root][i]!=fa) {//它的孩子不能是父节点
son[s++]=adj[root][i];//孩子加1
cost[adj[root][i]]=w[root][i];把边权值储存在孩子上
}

if (k<=0) return 0;//如果只留0条枝干(即什么都不留),那么一个苹果也没有

if (s==0) return -oo;//叶节点的情况

if (F[root][k]!=-oo) return F[root][k];//记忆化

int maxx=-oo+4;

for (int i=0; i<=k; i++) {
int s1=0,s2=0;
if (i>0)
s1=dfs(root,son[0],i-1)+cost[son[0]];//左子树的情况

if (k-i>0 && son[1]!=0)
s2=dfs(root,son[1],k-i-1)+cost[son[1]];//右子树的情况

maxx=(s1+s2>maxx)?s1+s2:maxx;//求最大值
}

F[root][k]=maxx;//记忆化

return maxx;
}

int main(){
in_();//读入,留意注意点部分

fout << dfs(-1,1,K) << endl;
return 0;
}

例题5:战略游戏

【题目】给定一棵树,每一个点可以放上一个士兵,也可以不放。如果放上一个士兵,那么他可以看到,与之相连的所有边。问,在所有边都能看到的情况下,最少需要多少士兵?

【输入】

4

0 1 1

1 2 2 3

2 0

3 0

【输出】

1

【分析】我们还是一样,先找子问题。其实这一道题,无非就是权衡一个点放还是不放。

我们用F[i][0]表示节点i不放士兵的情况,F[i][1]表示节点i放士兵的情况。

如果放,如图:

他不见了。

那么他的两个孩子,或是不放,没有什么所谓。所以,我们算两个还子放或是不放的最优值之和,加1,不就是结果吗?即:

他不见了。

如果不放,如图:

他不见了。

那么,它的孩子就一定要放。如果孩子也不妨,那么根节点与孩子的连线,就没人看守,不符合题意。即:

他不见了。

如果当前节点没有孩子(叶节点),那么

他不见了。

,以及

他不见了。

【技巧】这一题,我们需要从叶节点倒推到根结点,那么,我们可以bfs,把节点bfs一边,再反过来遍历,不就是我们想要的顺序吗?不仅仅是这道题,很多有关树形的DP,都是这么解决顺序问题的。

【程序】

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
80
81
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("Strategy_Game.in");
ofstream fout("Strategy_Game.out");

#define maxn 1000+10

vector <int> tree[maxn];
vector <int> queue_;
int F[maxn][2];
int N;

void in_() {
fin >> N;
for (int i=0; i!=N; ++i) {
int tmp_i,k;
fin >> tmp_i >> k;
for (int j=0; j!=k; ++j) {
int x;
fin >> x;
tree[tmp_i].push_back(x);
}
}
}

void bfs() {
int head=0,tail=0;
queue_.push_back(0);

while (head<=tail) {
int tmp=queue_[head];
for (int i=0; i!=tree[tmp].size(); ++i) {
queue_.push_back(tree[tmp][i]);

tail++;
}
head++;
}

for (int i=0; i*2!=N; ++i)
swap(queue_[i],queue_[N-i-1]);
}

void solve() {
for (int i=0; i!=N; ++i) {
int root=queue_[i];//当前节点

for (int j=0; j!=tree[root].size(); ++j) {//枚举孩子节点
int children;
children=tree[root][j];

F[root][0]+=F[children][1];//不放士兵的情况
F[root][1]+=min(F[children][0],F[children][1]);//放士兵的情况
}

if (tree[root].size()!=0)
F[root][1]++;//放了士兵,所以士兵数要加以1

if (tree[root].size()==0){//叶节点的情况
F[root][0]=0;
F[root][1]=1;
}
}
}

void out_() {
fout << min(F[0][0],F[0][1]) << endl;
}

int main() {
in_();

bfs();//bfs得出DP所需要的顺序

solve();

out_();
return 0;
}
Thank you so much.