动态规划的分类解析

动态规划动态规划什么是动态规划动态规划的条件动态规划的关键几种常见动态规划的种类例题分析什么是动态规划动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题但是经分解得到的子问题往往不是相互独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了很多次。假如能够保存已解决的子问题的答案，而在须要时再找出已求得的答案，就可以避开大量重复计算，从而得到多项式时间算法。

由此不难得出结论：动态规划实质就是记忆化搜寻下面这个数塔的例子将形象地向我们展示这样的结论给你一个数字三角形,形式如下: 1 23 8518 142110 找出从第一层到最终一层的一条 路,使得所经过的权值之和最小或 者最大.当然，大家都很清晰的知道转移方程为opt[i][j]=max{opt[i-1][j],opt[i-1][j-1]}+a[i][j]，边界条件特殊处理即可。但只要细致想想就会发觉，这不过是一个加了强力剪枝的记忆化搜寻而已，因为每个点我们只记录到当前节点的最优解，因此省去了大量的重复计数和明显不是最优解的状况，从而使运行速度有了极大的优化动态规划的条件 而在求解的过程中一道能运用动规解决的题必需具备以下几个条件无后效性,即某阶段的状态一旦确定，则此后过程的演化不再受此前各状态及决策的影响。也就是说，“将来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程将来的演化。满足最优子结构性质，即一个问题的最优解必需是在子问题取得最优解的状况下决策出来的动态规划的过程可以简洁地描述为找出最优解的性质，并刻画其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。依据计算最优值时得到的信息，构造最优解。动态规划的关键有明确的状态状态转移方程清晰正确几种常见动规的种类线性动规背包问题区间动规树形动规下面让我们通过几个例子来了解这些基本动规的思索方法拦截导弹（Noip2002）某国为了防卫敌国的导弹攻击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达随意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕获到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截全部的导弹。输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹。状态的确定状态的表示——f[i]，表示当第i个导弹必需拦截时，前i个导弹中最多能拦截多少。每个导弹有确定的高度，当前状态就是以第i个导弹为最终一个拦截的导弹。以前状态就是在这个导弹之前拦截的那个导弹。对于f[i]，我们考察在i之前位置的导弹，找到全部可以连接上的导弹k（即满足其高度大于等于第i个导弹），选择其中f[k]值最大的一个，f[i]=f[k]+1；假如没有满足条件的k，则f[i]=1。这是线性动态规划的经典例题。代码for(inti=1;i<=n;i++) scanf("%d",&a[i]);for(inti=1;i<=n;i++){ intmx=1; for(intj=1;j<i;j++) if(a[j]>=a[i])mx=max(mx,f[j]+1); f[i]=mx;}intans=0;for(inti=1;i<=n;i++) ans=max(ans,f[i]);printf("%d\n",ans);最低通行费一个商人穿过一个N*N的正方形的网格，去参与一个特殊重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必需在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都须要缴纳确定的费用。这个商人期望在规定时间内用最少费用穿越出去。请问至少须要多少费用？留意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。最低通行费输入第一行是一个整数，表示正方形的宽度N(1<=N<100)；后面N行，每行N个不大于100的整数，为网格上每个小方格的费用。输出至少须要的费用。分析这个问题的关键在于发觉对移动方向的限制：即由于必需在(2N-1)单位时间内完成移动，因此仅能向下或者向右移动。当移动方向限定后，不难看出这个问题就是变形的数塔问题，于是可以借助动态规划高效解决。状态的确定我们用opt[i][j]表示从左上角入口移动到第i行j列的最小代价。则opt[i,j]=min{opt[i-1][j],opt[i][j-1])+a[i][j];最终输出opt[n][n];代码for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)scanf(“%d”,&a[i][j]);for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];printf(“%d\n”,f[n][n]);乘积最大国际数学联盟确定的“2000—世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛活动，你的好挚友XZ也有幸得以参与。活动中，主持人给全部参与活动的选手出了这样一道题目：设有一个长度为N(N≤40)的数字串，要求选手运用M(M≤6)个乘号将它分成M+1个部分，找出一种分法，使得这M+1个部分的乘积最大。同时，为了帮助选手能够理解题意，主持人还举了如下一个例子：有一个数字串：312，当N=3，M=1时会有两种分法：⑴3×12=36⑵31×2=62这时，符合题目要求的结果是：31×2=62。现在，请你帮助你的好挚友XZ设计一个程序，求得正确的答案。分析由于自然数位数的上限为40，乘号数的上限为6，因此最大乘积位数的上限接近42位。明显，运算任何整数类型都无法容纳如此之大的数据，只能接受高精度运算，限于篇幅，对于高精度的加法运算、乘法运算和比较大小的运算，这里不作介绍，只是对的乘号最佳插入方式进行探讨：假设s1‥si(2≤i≤n)中插入j个乘号，其中s1‥sk中插入了j-1个乘号，即乘式中的第j+1项为sk+1‥si(j≤k≤i-1)：分析设ans[i][j]——长度为i的数串中插入j个乘号的最大乘积（整型数组）。明显ans[i][0]=s1..si对应的整型数组；ans[i][j]=max{ans[k][j-1]×sk+1..si}（1≤i≤n，1≤j≤min{i-1,m}，j≤k≤i-1）ans[n][m]即为其解。分析由于乘式中第j+1项sk+1‥si为常量，因此要使得ans[i][j]最大，则s1‥sk中插入j-1个乘号的乘积必需最大；同样，为了找寻第j个乘号的最佳插入位置，必需一一查阅子问题ans[j][j-1]‥ans[i-1][j-1]的解。明显该问题具备无后效性、最优子结构的特征，适用于动态规划方法。状态的确定我们用ans[i][j]表示前i个字符插入j个乘号可以获得的最大值则有：ans[i][0]=s1..sians[i][j]=max{ans[k][j-1]×sk+1..si}(j≤k≤i-1)ans[n][m]即为其解。代码输入n，m和数串s；fori←1tondoans[i][0]←s1..si对应的整数数组；fori←2tondo

{阶段：枚举数串的长度}forj←1tomin{i-1,m}do

{状态：枚举长度为i的数串中插入的乘号个数}fork←jtoi-1do{决策：枚举第j个乘号的插入位置}beginnext←sk+1..si对应的整数数组；

{计算第j+1项}ans[i][j]←max{ans[i][j]，

ans[k][j-1]×next}；

{计算状态转移方程}end；{for}输出最大乘积ans[n][m]；过河在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很厌烦踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点起先，不停的向终点方向跳动。一次跳动的距离是S到T之间的随意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳动的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少须要踩到的石子数。

分析从正面来考虑的话，这个问题是一个搜寻性的问题，须要考虑从当前点动身可以跳到的全部点。然而从反面考虑的话，我们只须要考虑那些能到用一步到达当前点的全部点中，踩到石头数最小的那个。即opt[i]=min{opt[k](max{0,i-t}≤k≤i-s)}+bri[i];代码Fori←1tondoopt[i]=10000000;opt[0]=0;Fori←stoL+tdofork←max{0,i-t}toi-sdoif(opt[k]+bri[i]<opt[i])opt[i]=opt[k]+bri[i];以上都是线性动规的一些例题，它们的基础时间困难度都是O(N2)装箱问题有一个箱子容量为maxv(正整数，maxv≤20000)，同时有n件物品(0≤n≤30)，每件物品有一个体积vi(正整数)。要求从这n件物品中任取若干件装入箱内，使箱子的剩余空间最小。分析这是一个最基础的背包问题，只须要考虑选取哪几个物品放入箱子，可以使得剩余体积最小。这道题的基本做法当然还是穷举放进背包的物品编号。若我们把取该物品记为1，不取该物品记为0，那么运用某种放入方式将对应一个2进制串，因此这类问题也被称为0-1背包问题.假如我们不从物品角度考虑，而是从体积角度考虑的话，就会发觉，这个问题还可以被描述为，w[i]的体积是否能由这些物品得到。状态的确定我们用opt[i][j]（布尔）表示前i个物品是否能达到j体积。则opt[i][j]的值取决于前i-1个物品能否达到j体积，或者是前i-1个物品能否达到j-v[i]体积则有opt[i][j]=(opt[i-1][j-v[i]])or(opt[i-1][j])初值为opt[0][0]=true；其他都为false代码memset(opt,0,sizeof(opt));opt[0][0]=1;for(inti=1;i<=n;i++)for(intj=0;j<=maxv;j++)if(j>=v[i]){opt[i][j]=opt[i-1][j]|opt[i-1][j-v[i]];}elseopt[i][j]=opt[i-1][j];采药辰辰是个天资聪颖的孩子，他的幻想是成为世界上最宏大的医师。为此，他想拜旁边最有威望的医师为师。医师为了推断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都须要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。假如你是一个聪慧的孩子，你应当可以让采到的草药的总价值最大。”

输入的第一行有两个整数T(1≤T≤1000)和N(1≤N≤100)，用一个空格隔开，T代表总共能够用来采药的时间，N代表山洞里的草药的数目。接下来的N行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

分析和上面一个问题一样，这个问题同样可以接受搜寻解决，然而搜寻的时间困难度也同样相当的可怕。那我们可不行以借鉴一下上面的想法来解决这个问题呢？状态的确定答案是确定的。类似地，我们用opt[i][j]表示前i个物体在j时间内的一个参数。但是我们在里面存的值并不是能否达到，而是在这个状态下可以达到的最大价值。但是状态的转移方程略微有些差别，除了考虑opt[i-1][j-t[i]]和opt[i-1][j]之外，还要考虑opt[i][j-1](这样可以最终干脆输出opt[n][maxt]从而省掉一次扫描)，即opt[i][j]表示前i个物体在j时间内可以达到的最大价值，留意这里包括不足j时间的状况。代码memset(opt,0,sizeof(opt));opt[0][0]=0;for(inti=1;i<=n;i++)for(intj=1;j<=maxt;j++)if(j>=v[i]){opt[i][j]=max{opt[i-1][j],opt[i-1][j-t[i]]+value[i],opt[i][j-1]}}elseopt[i][j]=max{opt[i-1][j],opt[i][j-1]};printf("%d\n",opt[n][maxt]);DairyQueen奶牛Bassie去DQ打工，遇到一个客人给了一张好大面值的钞票，于是Bassie不得不为了给这位顾客找零而面对这样一个问题：现在店里一共有n种硬币，对这些不同种的硬币进行编号，编号为i的硬币面值为a[i]。因为奶牛的手指头是有限的，因此他只能向你求助啦。(已知总需找零数为total)(1<=total<=1000,1<=n<=1000,1<=a[i]<=300)求一共有多少种解决方案？【输入】第一行为硬币总值total和硬币种类数n。以下n行为数值a[i]，i=1,2,3...n【输出】一行，解决方案数分析这道题目和上面的采药的区分仅仅在于，每个物品可以无限次的取。当然，这样的问题照旧可以用背包模型来解决，我们将这种模型称为无限背包。在这种状况下，我们只要把opt[i-1][j-a[i]]改成opt[i][j-a[i]],即允许一种物品被取多次。由于是计数，所以opt[i][j]=opt[i][j-a[i]]+opt[i-1][j]。一个重要的优化：我们可以把opt数组压缩成长度为total的一维数组，因为这样是不会影响结果的，但可以大大降低它的空间困难度。状态的确定我们用opt[j]表示硬币总面值为j时共有多少种方法opt[j]=opt[j]+opt[j-a[i]](i=1,2,3..n)代码memset(opt,0,sizeof(opt));opt[0]=1;for(inti=1;i<=n;i++) for(intj=a[i];j<=total;j++) opt[j]=opt[j]+opt[j-a[i]];printf("%d\n",opt[total]);多重背包[问题题目]有N种物品和一个容量为V的背包。第i种物品最多有m[i]件可用，每件体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包涵量，且价值总和最大。[输入样例]1003{maxv,n}704020{v1,v2,……,vn}504030{w1,w2,……,wn}123{m1,m2,m3……,mn}分析本题和无限背包问题很类似。基本的方程只需将无限背包问题的方程略微一改即可，因为对于第i种物品有m[i]+1种策略：取0件，取1件……取m[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大价值，则：f[i][v]=max{f[i-1][v-k×v[i]]+k×w[i]|0<=k<=m[i]}。时间困难度是O(V×∑m[i])。另一种好想好写的基本方法是转化为0-1有限背包求解：把第i种物品换成m[i]件该物品，即转化成了物品数为∑m[i]的0-1有限背包问题，干脆求解，困难度照旧是O(V×∑m[i])。但是我们期望将它转化为有限背包问题之后能够降低时间困难度。分析应用二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..m[i]件——均能等价于取若干件代换以后的物品。另外，取超过m[i]件的策略必不能出现。方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的体积和价值均是原来的体积和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),m[i]-2^k+1，且k是满足m[i]-2^k+1>0的最大整数。例如，假如m[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。分成的这几件物品的系数和为m[i]，表明不行能取多于m[i]件。另外这种方法也能保证对于0..m[i]间的每一个整数，均可以用若干个系数的和表示。这样就将第i种物品分成了(logm[i])种物品，将原问题转化为了困难度为O(V×∑logm[i])的有限背包问题，是很大的改进。k=0;//转化后物品的个数for(inti=1;i<=n;i++){//对第i件物品进行组合

intt=1;while(m[i]>0){if(m[i]>=t){k++;v1[k]=v[i]*t;w1[k]=w[i]*t;m[i]=m[i]-t;t<<=1;}else{k++;v1[k]=v[i]*m[i];w1[k]=w[i]*m[i]; m[i]=0;}}}代码for(inti=1;i<=n;i++){//01背包，留意n是转化后的物品个数for(intj=maxv;j>=v[i];j--){if(opt[j-v1[i]]+w1[i]>opt[j])opt[j]=opt[j-v1[i]]+w1[i];if(opt[j]>best)best=opt[j];}printf("%d\n",best);代码以上都是背包问题的一些例题，他们的基础时间困难度都是O(mn)的最小代价子母树问题描述：

有n堆沙子排成一排，每堆沙子有一个数量，例如：13

7

8

16

21

4

18。随意2堆相邻的沙子可以进行合并，将两堆沙子合并为一堆时，两堆沙子数量的和称为合并这两堆沙子的代价。经过不断的归并，最终将这些沙子归为一堆，而全部归并代价的和称为总代价。例如上列数，其中2种归并方案的代价为：第1种的总代价为20+24+25+44+69+87=267

第2种的总代价为15+37+22+28+59+87=248

由此可见，不同的归并过程得到的总代价是不一样的。

问题：当n个数给出后，找出一种合理的归并方法，使得总代价最小。分析（1）假如把归并1~4堆看成整个问题，则这个问题可以分解为三个归并方案，每个归并方案包含1~2个子问题：

①先归并1~3；再与4归并②归并1~2，归并3~4；再归并③归并2~4；再与1归并（2）假如我们接着分析增加更多堆数进行归并的问题，就会发觉n个数归并时，会分解为n-1种类型：Case1:归并第1堆，归并2~n堆；再最终归并Case2:归并1~2堆，归并3~n堆；再最终归并……

Casen-1:归并1~n-1堆，归并第n堆；再最终归并分析通过前面的分析，我们看到，归并代价事实上由两部分组成：（1）归并树左右子树的最小代价之和（2）归并树全部叶结点的权值之和而对于opt数组中的子区间数值的取值大小，我们有两种渠道来获得：（1）利用一般的dp，枚举起先结点和区间长度来进行DP（2）记忆化搜寻状态的确定我们用opt[i,j]表示i-j区间合并成一堆的最小代价，则有上面的结论有opt[i][j]=min{opt[i][k]+opt[k+1][j](k=i..j-1)}+value[i..j];opt[i][i]=value[i];代码for(inti=1;i<=n;i++)for(intj=i;j<=n;j++)opt[i][j]=10001000;for(inti=1;i<=n;i++)opt[i][i]=value[i];a[0]=0;for(inti=1;i<=n;i++)v[i]=v[i-1]+value[i];for(intj=2;j<=n;j++)for(inti=1;i<=n-j+1;i++)for(intk=i;k<=i+j-2;k++)if(opt[i][i+j-1]>opt[i][k]+opt[k+1][i+j-1]+v[i+j-1]-v[i-1])opt[i][i+j-1]=opt[i][k]+opt[k+1][i+j-1]+v[i+j-1]-v[i-1];printf("%d\n",opt[1][n]);Power多瑞卡得到了一份好玩而高薪的工作。每天早晨他必需关掉他所在村庄的街灯。全部的街灯都被设置在一条直路的同一侧。多瑞卡每晚到早晨5点钟都在晚会上，然后他起先关灯。起先时，他站在某一盏路灯的旁边。每盏灯都有一个给定功率的电灯泡，因为多端卡有着自觉的节能意识，他希望在耗能总数最少的状况下将全部的灯关掉。多端卡因为太累了，所以只能以1m/s的速度行走。关灯不须要花费额外的时间，因为当他通过时就能将灯关掉。编写程序，计算在给定路灯位置，灯泡功率以及多瑞卡的起始位置的状况下关掉全部的灯的最少耗能。Power输入第一行包含一个整数N，2≤N≤1000，表示该村庄路灯的数量。其次行包含一个整数V，1≤V≤N，表示多瑞卡起先关灯的路灯号码。接下来的N行中，每行包含两个用空格隔开的整数D和W，用来描述每盏灯的参数，其中0≤D,W≤1000。D表示该路灯与村庄起先处的距离(用米为单位来表示)，W表示灯泡的功率，每秒种该灯泡所消耗的能量数。路灯是按依次给定的。输出一行，包含一个整数，即消耗能量之和的最小值。留意结果不超过1,000,000,000。分析首先，我们必需明确这样一个决策：我们关掉的灯必定是一个连续的区间，也就是说，我们在路过的时候确定会把灯顺手关掉，不然确定不是最优解。而在关掉一个区间之后，我们须要作出的确定就是，回头关另外一边的灯还是接着朝当前方向走关前面的灯。对于我们的最终求解区间i..j,有2种可能：最终关第j盏灯，或者最终关第i盏灯。分析为了实现对这两种状况的记录，我们须要两个数组，分别存放关完[i,j]区间的全部路灯后分别站在两个端点时最小的电能消耗值。并且这两个数组中，[k][gdje]（k=1.2.3...gdje-1）区间的数值和[gdje][k](k=gdje+1...n)区间的数值都是很简洁确定的(gdje为起先位置)。在下面的动规过程中，我们只须要决策是须要转向另外一边还是接着走下去就可以了。状态的确定我们用left[i][j]表示关完灯后人站在i点所消耗的最小电能，用right[i][j]表示关完灯后人站在j点所消耗的最小电能，则有left[i][j]=min{left[i+l][j]+(value[1..i]+value[j+1..n])*(pos[i+1]-pos[i]),right[i+l][j]+(value[1][i]+value[j+1..n])*(pos[j]-pos[i])};right[i][j]=min{left[i][j-1]+(value[1..i-1]+value[j..n])*(pos[j]-pos[i])),right[i][j-1]+(value[1..i-1]+value[j..n])*(pos[j]-pos[j-1])}加分二叉树设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n)，其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数)，记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree(也包含tree本身)的加分计算方法如下：(subtree的左子树的加分)×(subtree的右子树的加分)＋subtree的根的分数

若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出；(1)tree的最高加分(2)tree的前序遍历加分二叉树【输入格式】第1行：一个整数n(n＜30)，为节点个数。第2行：n个用空格隔开的整数，为每个节点的分数(分数＜100)【输出格式】第1行：一个整数，为最高加分(结果不会超过4,000,000,000)。第2行：n个用空格隔开的整数，为该树的前序遍历。【输入样例】5571210输出样例14531245分析我们可以发觉这道题目给我们供应了一段序列，我们须要做的就是每次选取一个断开的点，然后把问题递归地求解就可以了。这就为我们的动规供应了条件：具有最优子结构性质。我们须要做出的决策，仅仅是从当前序列中选取一个点作为当前子树的根节点，所以动规的转移是O(n)的。状态的确定我们用opt[i][j]表示在[i..j]区间内可以获得的最大加分，用root[i][j]表示[i..j]范围内选取哪个结点作为根时可以获得最大加分。对区间[i,j](i>j)，我们定义opt[i][j]=1;则有：opt[i][j]=max{opt[i][k-1]*opt[k+1][j]+value[k]|k=i,i+1,i+2..j}root[i][j]为对应的k值intsearch(intl,intr){if(opt[l][r]!=0)returnopt[l][r];for(inti=l;i<=r;i++)if(search(l,i-1)*search(i+1,r)+value[i]>opt[l][r]){opt[l][r]=search(l,i-1)*search(i+1,r)+value[i];root[l][r]=i;}}memset(opt,0,sizeof(opt));for(inti=1;i<=n+1;i++)opt[i][i-1]=1;for(inti=1;i<=n;i++)opt[i][i]=value[i];intAns=search(1,n);代码上面几道题是区间动态规划的一些例题，它们的基础时间困难度都是O(N3)的聚会的快乐(Party)你要组织一个由你公司的人参与的聚会。你希望聚会特殊快乐，尽可能多地找些好玩的人。但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。给定N个人（姓名，他幽默的系数，以及他上司的名字），找到能使幽默系数和最大的若干个人。输入第一行一个整数N（N<100）。接下来有N行，每一行描述一个人，信息之间用空格隔开。姓名是长度不超过20的字符串。幽默系数是在0到100之间的整数输出邀请的人最大的幽默系数和分析细致看过这个问题之后，会发觉这道题目和我们上面遇到的一些类型的动态规划都有点区分：它的数据并不是以线性或者表格的形式，而是以树的形式进行存储的。可以发觉，这道题目中的关系可以简洁地描述为：在一棵树中，父亲结点和儿子结点不行以同时选取。而每个结点有一个权值，在满足上述条件的状况下求出可以选取出的最大值。这就是我们所说的树形动态规划。由于树本身的递归性质，我们运用记忆化搜寻的方法来完成子问题答案的存储。状态的确定明显，对于每个结点我们须要记录当前结点是否被取到，以及在该种状况下该子树所能获得的最大幽默系数。因此，我们定义opt[1][i]表示在编号为i的结点必取的状况下以i为根的子树所能获得的最大快乐值；相应地，opt[0][i]表示在编号为i的结点不取的状况下以i为根的子树所能获得的最大幽默系数。则依据题目中的要求，我们有opt[1][i]=value[i]+Σopt[0][k](k为全部i的子结点的编号)opt[0][i]=Σmax{opt[0][k],opt[1][k]}(k为全部i的子结点的编号)w数组用来存储边；r[i]存放编号为i的结点的儿子数；d[i]中存放编号为i的结点的在w数组中最终一条边的编号，其中d[0]=0;d[i]=d[i-1]+r[i];intsearch(intflag,intlab){//记忆化搜寻if(opt[flag][lab]!=0)returnopt[flag][lab];intp=(flag==1)?value[lab]:0;for(inti=d[lab-1];i<=d[lab];i++)if(flag==1)p+=search(0,w[i]);elsep+=max(search(0,w[i]),search(1,w[i]));opt[flag][lab]=p;returnp;}memset(d,0,sizeof(d));for(inti=1;i<=n;i++)d[i]=d[i-1]+r[i];ans=max(search(1,root),search(0,root));代码二*苹果树有一棵苹果树，假如树枝有分叉，确定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号确定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树现在这颗树枝条太多了，须要剪枝。但是一些树枝上长有苹果。给定须要保留的树枝数量，求出最多能留住多少苹果。二*苹果树输入格式第1行2个数，N和Q(1<=Q<=N,1<N<=100)。N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

每根树枝上的苹果不超过30000个。输出格式一个数，最多能留住的苹果的数量。分析同样，这道题目给出的数据是以树形结构连接的。而且这道题很明确的告知我们：每个结点只可能是叶节点或者拥有两个儿子。因此，我们可以探讨每个结点伸出的两个树枝的剪枝状况，并且照旧用记忆化搜寻完成。状态的确定我们用opt[i][j]表示编号为i的结点作为根的子树中保留j个树枝可以获得的最大苹果数。状态转移方程为：opt[i][j]:=maxopt[i.rc][j-1]+value[i.rc],(剪掉左枝)opt[i.lc][j-1]+value[i.lc],(剪掉右枝)max{opt[i.lc][k]+opt[i.rc][j-2-k]+value[i.lc]+value[i.rc]}(0<=k<=j-2)(左枝和右枝都不剪)intsearch(intlab,intnum){if(opt[lab][num]!=0)returnopt[lab][num];if(lc[lab]==0||num==0)return0;intl=lc[lab],r=rc[lab];if(search(r,num-1)+value[r]>opt[lab][num])opt[lab][num]=opt[r][num-1]+value[r];if(search(l,num-1)+value[l]>opt[lab][num])opt[lab][num]=opt[l][num-1]+value[i];for(inti=0;i<=num-2;i++)if(search(l,i)+search(r,num-2-i)+value[l]+value[r]>opt[lab][n