【算法?日更?第九期】树型动态规划详解:二叉苹果树

▎前置技能:动态规划&树

  树型动态规划一听就知道是在树结构上使用的动态规划,那么不会树结构和动态规划怎么行?戳这里了解动态规划

▎什么是树型动态规划?

?『定义』

  树形动态规划问题可以分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题,称为多阶段决策问题。(copy自百度)

  猜你也不愿意看,简单说就是掺了树的动态规划呗,也特别不到哪里去,只要树结构掌握的不错就行了。

?『为什么有树型动态规划,而没听说过图型动态规划、队列型动态规划什么的呢?』

  这个很容易理解,因为树这个数据结构很特殊,只有一个前驱,有多个后继,本就是一个纯天然的递归结构,而动态规划常用什么方法呢?数组递推和记忆化搜索,巧了!记忆化搜索正是递归的方式,这同时也暗示着一件事:树型动态规划是不能使用数组递推的!要用记忆化搜索。

?『树型动态规划的方向』

  ①由叶到根:也就是从叶子结点(递归边界)向根节点(原问题)不断返回,最终在根节点(原问题)处得到答案。这种树型动态规划的方向很常见,也是我们平时使用递归时的方式。

  ②由根到叶:这种题目很不常见,主要就是将所有点当做一次根节点进行求值,然后有父节点向子节点转移信息。

?『树型动态规划的顺序』

  树型动态规划可以理解为后序遍历,也就是先处理好子节点,再返回处理父节点。

▎树型动态规划的解题技巧

?『树型动态规划的一般步骤』

  ①建树:树型动态规划叫个这名字,总得有树吧,所以,一定要先建树,建树时要注意恰当的存储方式,数据规模较小时使用邻接矩阵,较大时使用邻接表,至于指针大佬就请默默走开。

  ②设计状态:动态规划怎么也得有状态了吧,一般树型动态规划通常是1~2维,所以时间复杂度一般不高,不过只有状态设计好了,才能正常的进行后续流程。

  ③状态转移方程:这是令人最讨厌的东西,纯找规律,要找到父节点和子节点之间的关系,才能写出来。

  ④确定答案:有些题目的答案需要推理一下,不过很多不需要,这也和状态的设计有关。

?『怎么判断题目是否适用于树型动态规划』

  ①长得就是树型动态规划题,比如后面的二叉苹果树那道题;

  ②先判断是否是动态规划,是否符合动态规划的三大性质;

  ③是否需要树;

▎实战演练

  提起一棵苹果树,你会想到什么?

  砸到牛顿头上的那个苹果?

  被乔布斯啃了一口的苹果?

  这可苹果树上可不一般,这是我见过的最奇葩的树。

  废话不多说,直接上题:


1575:【例 1】二叉苹果树


时间限制: 1000 ms         内存限制: 524288 KB
提交数: 175     通过数: 104 

【题目描述】

有一棵二叉苹果树,如果数字有分叉,一定是分两叉,即没有只有一个儿子的节点。这棵树共 N 个节点,标号 1 至 N,树根编号一定为 1。

我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树,因为树枝太多了,需要剪枝。但是一些树枝上长有苹果,给定需要保留的树枝数量,求最多能留住多少苹果。

【算法?日更?第九期】树型动态规划详解:二叉苹果树

【输入】

第一行两个数 N 和 Q ,N 表示树的节点数,Q 表示要保留的树枝数量。

接下来 N−1 行描述树枝信息,每行三个整数,前两个是它连接的节点的编号,第三个数是这根树枝上苹果数量。

【输出】

输出仅一行,表示最多能留住的苹果的数量。

【输入样例】

5 2
1 3 1
1 4 10
2 3 20
3 5 20

【输出样例】

21

【提示】

数据范围与提示:

对于 100% 的数据,1≤Q≤N≤100,N≠1,每根树枝上苹果不超过 30000 个。

【来源】


  这道题一看就知道是树型动态规划,因为这分明就是一道树型动态规划题,那么怎么做呢?

Part one 建树

  假设每行输入分别对应的变量是a,b,c。

  先来考虑建树,建树都是应该递归建的,请看一下别人博客,一般都是这样的。小编的建树方式不太一样,那就是一直判断,如果b没有父节点,那么那么b就是a的子节点,存起来;如果b有父节点,那么a就是b的子节点,存起来。

  那么左右子树呢?顺序没有任何关系,所以先存左子树,后存右子树,代码比较简单,就不过多解释了:

 1 cin>>n>>q;
 2     for(int i=1;i<=n-1;i++)
 3     {
 4         cin>>a>>b>>c;
 5         if(father[b]!=0) 
 6         {
 7             father[a]=b;
 8             if(leftchild[b]==0) leftchild[b]=a;
 9             else rightchild[b]=a;
10         }
11         else 
12         {
13             father[b]=a;
14             if(leftchild[a]==0) leftchild[a]=b;
15             else rightchild[a]=b;
16         }
17         apple[a][b]=c;
18         apple[b][a]=c;
19     }

Part two 设计状态

  我们是要求以根节点保留q条枝条能保留的最多苹果数。那么不妨将f[i][j]表示为以i为根节点保留j条枝条能保留的最多苹果数。

Part three 状态转移方程

  那么现在来考虑一件事,我们需要向左右两边分一些枝条量,各是k-1和j-k-1个(假设左子树有k个),为什么都减一呢?小编在调试代码的过程中发现:如果不减一,那么左右两边都会多分一个枝条,原因是转移时忘了转移的节点和原节点间有一个枝条。

  【算法?日更?第九期】树型动态规划详解:二叉苹果树

 

  所以方程是这样的f[i][j]=max{f[leftchild[i]][k-1]+f[rightchild[i]][j-k-1]+apple[i][leftchild[i]]+apple[i][rightchild[i]]},同时要记得先特判k=0和k=j的情况,小编稍微改了改,就是这个熊样:

 1 for(int k=0;k<=j;k++)
 2     {
 3         int l=dp(leftchild[i],k-1);
 4         int r=dp(rightchild[i],j-k-1);
 5         if(k==0) x=r+apple[i][rightchild[i]];
 6         else if(k==j) x=l+apple[i][leftchild[i]];
 7         else x=l+r+apple[i][leftchild[i]]+apple[i][rightchild[i]];
 8         if(x>f[i][j])
 9         f[i][j]=x;
10     }

 Part four 确定答案

  小编可能设计的状态不太和别人一样,看见别人的博客答案和我的不一样,还有设计三维的,别人的答案:f[1][q+1];小编的答案:f[1][q]

 Part five 一点忠告

  小编是这样过的这道题的:

【算法?日更?第九期】树型动态规划详解:二叉苹果树

  猜猜小编是怎么错的?小编显示忘了删测试代码和记忆化,一直以为哪里有不可告人的错误,结果被忘了删测试代码纠结了很长时间。

  好了,代码如下:

 1 #include<iostream>
 2 using namespace std;
 3 int leftchild[1000]={0},rightchild[1000]={0},father[1000],apple[1000][1000],f[1000][1000],n,q,a,b,c;
 4 int dp(int i,int j)
 5 {
 6     if(j<=0) return 0;//边界条件必须考虑周全 
 7     if(leftchild[i]==0) return 0;
 8     if(f[i][j]) return f[i][j];//记忆化 
 9     if(j==1) //只剩1根枝条,那么肯定是选那根苹果多的呗 
10     {
11         return max(apple[i][leftchild[i]],apple[i][rightchild[i]]);
12     }
13     int maxn=-1,x;
14     for(int k=0;k<=j;k++)
15     {
16         int l=dp(leftchild[i],k-1);
17         int r=dp(rightchild[i],j-k-1);
18         if(k==0) x=r+apple[i][rightchild[i]];
19         else if(k==j) x=l+apple[i][leftchild[i]];
20         else x=l+r+apple[i][leftchild[i]]+apple[i][rightchild[i]];
21         if(x>f[i][j])//因为两边各分多少枝条数量不确定,所以依次模拟选最优的方案 
22         f[i][j]=x;
23     }
24     return f[i][j];
25 }
26 int main()
27 {
28     cin>>n>>q;
29     for(int i=1;i<=n-1;i++)//建树 
30     {
31         cin>>a>>b>>c;
32         if(father[b]!=0) 
33         {
34             father[a]=b;
35             if(leftchild[b]==0) leftchild[b]=a;
36             else rightchild[b]=a;
37         }
38         else 
39         {
40             father[b]=a;
41             if(leftchild[a]==0) leftchild[a]=b;
42             else rightchild[a]=b;
43         }
44         apple[a][b]=c;
45         apple[b][a]=c;
46     }
47     cout<<dp(1,q);
48     return 0;
49 }

【算法?日更?第九期】树型动态规划详解:二叉苹果树

上一篇:iOS自动化探索(十)代码覆盖率统计


下一篇:iostream与iostream.h