POJ 2378 Tree Cutting

题意

变相考察求树的重心。

思路

和这个题一致

代码

 

POJ 1655 Balancing Act

题意

求树的重心。

思路

树的重心的定义是:选树中某个点i当作树的根,所有子树中最大的那棵的大小是Si,整棵树中能令Si最小的那个点,就是树的重心。

求重心是作为树分治的一个环节出现的,只有保证了每一次点分治的位置都是重心才能保证树分治的复杂度为O(nlogn)。

求重心的想法是树dp,对于每个节点都要存储他所有孩子对应的子树中最大子树的大小,还要存储他的父亲是谁。求好了这些数据之后,按着定义,就可以知道谁是重心了。

代码

 

动态规划初步

[toc]

什么是动态规划

  • 动态规划是一种方法,或者说思想,它并不是某种特定算法。
  • 动态规划方法的通俗解释:将原来比较复杂的问题分解为若干比较简单的子问题,将这些子问题逐个解决,并存储这些子问题的答案,原来的问题的答案将会从这些分解了的子问题的答案中导出。等到下一次遇到了相同的子问题时,我们只是提取出事前存储的问题的答案,而不是重新做一次计算。
  • 对上面通俗解释的解释:无论是原问题,还是子问题,都是问题,我们拿到一个问题,给他分解为若干子问题,那么接下来我们如何解决子问题?那就是把每个子问题当成原问题再度分解,得到子问题的子问题,然后为了解决这些“子问题的子问题”,我们再度分解。。。直到最终我们得到了已经无法再分的“原子问题”,我们假定原子问题是可以很好地被解决的,那么我们理论上只要解决的全部的原子问题,再回推,就可以解决掉全部子问题,最终解决最根本的问题,也就是我们拿到的问题。而动态规划方法体现在我们加速这个过程上,在问题的分解过程中,我们可能会遇到重复的情况,如果我们对这些重复的情况调用之前计算好的答案,就不用再次深入分解问题,这样能大大加快整个求解进程。
  • 动态规划的关键字:递推、记忆化、状态转移

状态

什么是状态

  • 字面含义:物质系统所处的状况。
  • 我们这里所说的状态是一种抽象观念。
  • 在动态规划的设计上,一个“状态”,表达的是在某个情形下的子问题。
  • 在动态规划的操作上,状态最终表现为一个又一个的值,也就是在某个特定情形下的子问题的答案。

状态转移

  • 基于当前状态和其他输入,移动到其他状态。
  • 说人话:某个东西现在是某个样子的,然后我对他动了些手脚,这个东西变成了另外一幅样子。
  • 当前状态能不能转移到当前状态?可以
  • 如何表达状态转移?
    • 状态转移方程(你可以列个公式)
    • 状态转移图(你可以把状态形象化为点,把转移条件形象化为边)
    • 状态转移表(你听说过函数表吗?虽然没怎么用过但这是初中内容。)

那么状态和动态规划有什么关系?

上面说到了,在动态规划里的“状态”表达的是“子问题”,前面也说了,动态规划整体来看是一个操作子问题的方法,这样我们也可以说动态规划是一个操作状态的方法。在动态规划过程中,我们分解当前状态,得到子状态,处理子状态,记忆子状态,最终处理好全部需要处理的状态,从所有状态中挑出合适的、我们需要的状态来代表最终答案。

用动态规划解决问题

必要条件

不是所有的问题都能用动态规划解决,能够使用动态规划方法解决的问题必须满足以下两个基本性质:

  • 对于一个问题,如果它取得了最优解,那么这个问题所能分解出来的所有子问题的解也是最优的,这个性质称为最优子问题/最优子结构
  • 如果我们已经解决了一些问题,那么当我们解决其他问题的时候,已经解决的问题的答案必须不能受新解决的问题影响。也就是说某个状态之后的过程不可以影响之前的状态。这一性质,称为无后效性

分治?

聪明的你发现了,分治法不也是把当前问题分解为小一点的问题直到不能再分,然后解决原子问题回推得到根问题的答案吗?分治和动态规划有什么区别?

适用于用动态规划法求解的问题,分解后的子问题往往不是独立的,在之后的求解过程中会用到之前已经解决的问题的答案。

上面说过了,动态规划过程中每个子问题的答案将会被保存以避免重复计算,这里才是我们高速解决问题的原因。因此我们有下面这种说法:

使用动态规划有意义的条件

  • 子问题之间不是独立的,一个子问题在之后的求解过程中可能会被多次使用到。这个性质称为重叠子问题
  • 需要注意重叠子问题并不是动态规划适用的必要条件,但是如果没有这个性质,使用动态规划并没有意义。

操作步骤

我们使用动态规划方法解决问题时,一般按照以下思维和操作程序:

  • 分析问题:判定其是否能且有意义使用动态规划。
  • 再度分析:找出将问题分解的方法,将分解后的问题合并的方法,确定原子问题的位置(即边界条件)。
  • 定义状态:确定每个状态对应的问题是什么,答案表示什么,携带的情形是什么。
  • 处理状态:递推 and/or 记忆化。
  • 选择答案:从处理好的状态中选择我们需要的合适的状态作出最终答案。

关键点

  • 状态设计
  • 转移方程
  • 初始化
  • 二次优化(本文不讨论)

如果把目光放长远一点

  • 动态规划方法解决了一个问题,但这很可能并不是你要解决的问题的全部。
  • 递推可以叫动态规划吗?我认为可以,你可以看成每个问题只能分解出一个子问题,虽然感觉上有一点奇怪,而且你要注意到递推过程中并没有重叠子问题,即使你管他叫动态规划,那也是没啥意义的动态规划。
  • 开一下脑洞:你用一种动态规划方法分解出来的原子问题需要另外一种动态规划方法解决?你现在动态规划解决的问题其实只是另一个问题的模块?想想就好了,高中生啥都干的出来。

一些经典且简单的模型

关于Fibonacci

广义/系数Fibonacci

首先要说的是,Fibonacci数列中,最有分量的一句话其实是f_i = f_{i-1} + f_{i-2}f_1f_2的值并不重要,所以我们在这里可以推广Fibonacci数列的含义为只要有这样的递推就可以称为(广义)Fibonacci数列。

我们都知道Fibonacci数列,要想快速应付多次查询我们可以事前预处理,要想快速应付一次巨大的查询我们可以使用矩阵快速幂。那么如果我给出下面的问题呢?

Given f_1 = a,f_2 = b,f_i = f_{i-1} + f_{i-2} for every f >= 3,for each query you will get 3 numbers a,b,c,you have to output f_c in condition of given a and b.

这个问题意外的简单,仔细观察我们就发现了,对于给出的这个数列的每一项,a的系数实际上是f_1=1,f_2=0的Fibonacci数列,b的系数实际上是f_1=0,f_2=1的Fibonacci数列,所以接下来怎么操作想必大家都很清楚。

Fibonacci的前缀和?

是的,也是Fibonacci数列。

前两项的作用

前两项事实上决定了整个Fibonacci数列,因此只要知道前两项,就相当于知道了整个Fibonacci数列。

数字三角形

问题

POJ 1163 The Triangle

解法

我们令A[i][j]表示金字塔从上往下数第i行第j个数。

我们令dp[i][j]表示从金字塔从上往下数第i行第j个数。

对于金字塔上每一个点,我们假定已经计算出了从这个点左下方出发走完金字塔的最优解和右下方走完金字塔的最优解,那么从这个点走完金子塔的最优解已经是从左下方或右下方走完这两个可能性中最优的那个,再加上当前这个点的数值,即:

dp[i][j] = best(dp[i+1][j],dp[i+1][j+1]) + A[i][j]

对于最后一行,因为已经是底部,所以dp[i][j] = A[i][j]

最后,我们需要的答案是从塔尖走完整个金字塔的最优解,即dp[1][1]。

问题解决。

背包问题

背包问题九讲

我们只关心这些内容:

  • 01背包
  • 完全背包
  • 多重背包
  • 滚动数组

最长上升子序列

问题

POJ 2533 Longest Ordered Subsequence

解法

令A[i]表示原数列第i位数。

令dp[i]表示检查到原数列第i位(且最后一位就是第i位)时的最长公共子序列长度。

那么对于没有解决的dp[i],我们依次检查所有在第j位之前的数,假设检查到了第j位:

  • 如果A[j] < A[i],那么我们可以选择在j位表示的最长上升子序列后面添附第i位数,这样得到了一种可能的dp[i]=dp[j]+1
  • 否则,我们只能选择放弃之前的结果,这样得到了一种可能的dp[i]=1
  • 我们综合所有可能的dp[i],选出最大的那个,保存

对于第1位,显然只有它自己一个构成了一个上升序列,因此dp[1] = 1。

这样我们完成了状态转移,最终结果就是dp数组中的最大值.

我们只关心O(n^2)的解法(还有一种O(nlogn)的解法)。

HDU5396 / 15多校9-1 Expression

题意

给出了一个算术表达式,表达式里面只会含有加减乘三种运算。我们每一次从中选取两个数字并执行这两个数字对应的运算,运算结果放回式子中继续进行运算,直到最后只剩下了一个数。让我们求的是每一种不同的选取方式所得到的结果的和。

注意

这个题没有做好的主要原因是没有领会到题目中关于不同的选取方式的定义,注意到题目中讲到只要有一轮选取的数字不一样,就视为不同。这句话的含义中有两个信息:一是允许重复,二是要分先后

思路

最开始确实是没什么思路的,后来看了看board发现并不是特别难的题。于是尝试拆解问题,我们可以从算数式的一小段入手,以sample的1 + 4 * 6 – 8 * 3为例。

只考虑1 + 4部分,只有一种配置方法,就是(1 + 4);
考虑1 + 4 * 6部分,我们发现这一部分可以看成两种情况:1 + (4 * 6)和(1 + 4) * 6,在这里面我们已经考虑了1 + 4区段,而4 * 6区段只有一种配置。这样1 + 4 * 6这个区段就有两种配置了。
接下来考虑1 + 4 * 6 – 8区段,要想得到这个区段的全部情况,我们应该考虑:
1 + (4 * 6 – 8),1 + 4 * (6 – 8),(1 + 4) * 6 – 8,(1 + 4 * 6) – 8这些情况,其中(4 * 6 – 8)又可以看成考虑(4 * 6) – 8,4 * (6 – 8)这两种情况,而(1 + 4 * 6)的对应情况我们先前已经算好了。
最后,考虑1 + 4 * 6 – 8 * 3,顺着上面的思路来,就可以拆分成:
1 + (4 * 6 – 8 * 3),1 + 4 * (6 – 8 * 3),(1 + 4) * 6 – (8 * 3),(1 + 4 * 6) – 8 * 3,(1 + 4 * 6 – 8) * 3,接下来再去拆分这五种情况中的子情况。。。

如果比较敏感的话应该已经发现这就是典型的区间dp了,在推方程的时候,我们是将所有子情况的答案累加,得到当前情况的答案,但这还不够,还要注意每种情况,因为选择顺序的关系,会有多重副本,而这个副本的数量其实蛮好求,就是阶乘,而还要注意,我们在讨论当前情况的时候,是将整个等待处理的算式区段分成了(左区段)算子(分界点)算子(右区段)这样看待的,那么先后的问题又来了,我们不光左右区段的答案自身要乘上阶乘,最后整个结果还要乘上一个组合数,因为左右区段的操作又是分先后的。

以下引自官方题解,注意第2段第2行的dp[l][r]实际上是dp[l][k]

 

QQ20150820-1@2x

代码

测试数据

 

SPOJ SORTBIT Sorted bit squence

[等待填坑]

 

URAL 1057 Amount of Degrees

[ 等待填坑中]

 

HDU 3669 Cross the Wall

题意

 

思路

需要一定的转化的斜率优化DP。

代码

 

HDU 2829 Lawrence

题意

本题和HDU 3507 Print Article如出一辙。都是给出了一个数列,和一个费用公式,要你设计一种把数列分为若干组之后计算出的总费用达到最小的方案。

思路

依然是斜率优化DP。不过本题有两个要点必须注意:1.我们默认炸毁了某一道路之后,就不要再去管默许炸毁了的道路之前的节点了。2.一定要注意DP数组的正确初始化(因为这个我挑通宵调试了近10小时)。

详细的状态转移方程还是建议自己推导,因为下标等微妙的细节稍有相左,就会产生错误,如果确信自己的方程没有问题不妨从上面几个要点调试。如果没有掌握斜率优化DP的基本知识,请移步HDU 3507 Print Article并仔细阅读教程。

代码

 

HDU 3507 Print Article

题意

给出了一个费用计算公式,现在要你把一个数列分成若干组,每一组分别套用给出的费用计算公式计算费用。你要设计一种方法使得总费用最小。

思路

本题的DP方程推导相对容易(不过我学艺不精被卡在了这一步),之后我们会发现导出的方程完全无法满足时间限制,这个时候通过对费用公式的变形可以导出一种适用于斜率优化DP的形式。

斜率优化的操作非常复杂,幸运的是已经有人写出了详实的教程:斜率优化DP。这篇教程基本是斜率优化教程中最好理解的了,并且以这个题为例题。建议学习时手动模拟操作过程,以便形象、深入地理解。

代码

实现斜率优化的要点:1.合理正确地推导出斜率的表示形式和所有的转移方程、决策判定条件。2.正确地选择大于小于号。3.单调队列的实现,同时注意单调队列无法使用STL很好地实现,只能数组模拟。4.正确地初始化DP数组(非常重要)。

 

SGU 195 New Year Bonus Grant

题意

某厂采用一种奇怪的方式发奖金,给出一个上下级关系树,大BOSS是1号根节点,别的员工都有自己的上司。对于每个员工,它有三种选择,要么接受上级下发的奖金,要么给所有下级发奖金,要么啥都不做(只有傻子才会这样,所以你可以当成没这种选择),大BOSS一定发奖金。只要一个员工选择收奖金,他就得到1000块。

现在要你设计一种方案,使得所有人收到的奖金的总数额最大。

思路

树DP解法

对于每一个节点,都有两种状态:选择收奖金,选择收奖金。

对于选择收奖金的节点的儿子节点,一定不可以选择收奖金。

对于选择发奖金的节点的儿子节点,可以选择收他的奖金,也可以选择发奖金。

这样就可以建立dp数组dp[a][0/1],a是节点对应的编号,0/1表示该节点选择收/发奖金的状态。利用DFS下潜到叶子节点之后,就可以开始树DP了。

状态转移的方程可以参考dfs()方法。

输出路径的话,只要记录下每一次的决策,DP结束之后反查就可以搞定。

贪心解法

引用自JHC23的Blog。

自底而顶遍历,如果自己的上级没有接受奖金(那么就能够把钱给发自己了),而自己也从不增接受奖金则可以获得奖金,同时标记自己和上级。这样下去就可以得到可得到最大奖金。

代码

树DP解法:

 

Scroll to top