NOIP普及讲座3-动态规划1

从搜索到动态规划点击添加文本点击添加文本点击添加文本点击添加文本引例（数塔问题）设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，从根结点13出发向左、向右的路径长度可以是： 13－11－7－14－7，其和为52 13－11－12－14－13，其和为63若要求从根结点开始， 请找出一条路径，使 路径之和最大,输出路

径的长度。1315141124131211876872612点击添加文本点击添加文本点击添加文本点击添加文本引例（数塔问题）【问题分析】 （1）贪心法点击添加文本点击添加文本点击添加文本点击添加文本引例（数塔问题）【问题分析】 （2）搜索：点击添加文本点击添加文本点击添加文本点击添加文本引例（数塔问题）【问题分析】

（3）动态规划：

点击添加文本点击添加文本点击添加文本点击添加文本引例（数塔问题）

1315141124131211876872612点击添加文本点击添加文本点击添加文本点击添加文本动态规划的基本概念（1）阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。（2）状态：状态表示每个阶段开始所处的自然状况和客观条件，它描述了研究问题过程中的状况。（3）决策：决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。点击添加文本点击添加文本点击添加文本点击添加文本动态规划的基本概念（4）策略和最优策略：由所有阶段的决策组成的决策序列称为全过程策略，简称策略。在实际问题中，从决策允许集合中找出最优效果的策略称为最优策略。（5）状态转移方程：状态转移方程是确定两个相邻阶段状态的演变过程。点击添加文本点击添加文本点击添加文本点击添加文本运用动态规划的条件（1）最优化

子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质。也就是说问题的一个最优解中包含着子问题的一个最优解。（2）无后效性

当前阶段中的状态只能由上一个阶段中的状态转移方程得来，与其他阶段的状态没有关系，特别是与未发生的阶段状态没有关系，这就是无后效性。点击添加文本点击添加文本点击添加文本点击添加文本动态规划算法的一般模式（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段；（2）确定状态和状态变量：将问题发展到各个阶段时所处的各种情况用不同状态表示出来；（3）确定决策并写出状态转移方程：一般是根据相邻两个阶段各状态之间的关系来确定决策；（4）寻找边界条件：给出的状态转移方程是一个递推式，必须有一个递推的边界条件；（5）编写程序。

点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题1】拦截导弹（noiopenjudge8780）问题描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹。点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解输入第一行是一个整数N（不超过15），表示导弹数。第二行包含N个整数，为导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）。输出一个整数，表示最多能拦截的导弹数。样例输入838920715530029917015865样例输出6点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态：f[i]代表打下第i颗导弹最多能打多少颗导弹方程：f[i]=max(f[j])+1(1<=j<i)且第i颗导弹的高度要高于第j颗导弹的高度

点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】

点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题2】饥饿的牛问题描述：牛在饲料槽前排好了队。饲料槽依次用1到N(1<=N<=2000)编号。每天晚上，一头幸运的牛根据约翰的规则，吃其中一些槽里的饲料。约翰提供B个区间的清单。一个区间是一对整数start-end,1<=start<=end<=N，表示一些连续的饲料槽，比如1-3,7-8,3-4等等。牛可以任意选择区间，但是牛选择的区间不能有重叠。当然，牛希望自己能够吃得越多越好。给出一些区间，帮助这只牛找一些区间，使它能吃到最多的东西。在上面的例子中，1-3和3-4是重叠的；聪明的牛选择{1-3，7-8}，这样可以吃到5个槽里的东西。点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【输入格式】第一行，整数B(1<=B<=1000)第2到B+1行，每行两个整数，表示一个区间，较小的端点在前面【输出格式】仅一个整数，表示最多能吃到多少个槽里的食物。【样例输入】3137834【样例输出】5

点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态：f[i]代表吃了第i个区间最多能多少食物方程：f[i]=max(f[j])+i个区间的长度(1<=j<i)且第i颗区间的开始时间要大于j的区间的结束时间

点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题3】最长公共子序列（codevs1408）问题描述：熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。小沐沐说，对于两个串A，B，如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【输入格式】第一行N，表示A，B的长度。第二行，串A。第三行，串B。【输出格式】输出长度【样例输入】422132123【样例输出】2【数据范围及提示】1<=N<=3000，A，B中的数字不超过maxlongint点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】

状态

f[i,j]代表a字符串到i,b字符串到j的最长公共字串方程：

a[i]=a[j]则f[i,j]=f[i-1,j-1]+1;a[i]不等于a[j]则f[i,j]=max(f[i-1,j],f[i,j-1])点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】

点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】

点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题4】最低通行费用（noiopenjudge7614）问题描述：一个商人穿过一个N*N的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。输入第一行是一个整数，表示正方形的宽度N(1<=N<100)；后面N行，每行N个不大于100的整数，为网格上每个小方格的费用。输出至少需要的费用.点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解样例输入51468102571517689182010111219212023252933样例输出109提示样例中，最小值为109=1+2+5+7+9+12+19+21+33。点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态：f[i,j]代表到达i,j位置的最低费用方程：f[i,j]=max(f[i-1,j],f[i,j-1])+a[i,j];

点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】

点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题5】机器分配问题描述：某总公司拥有高效生产设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为总公司提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。其中M<=100，N<=100。点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【输入格式】第一行为两个整数M，N。接下来是一个N×M的矩阵，其中矩阵的第i行的第j列的数Aij表明第i个公司分配j台机器的盈利。所有数据之间用一个空格分隔。【输出格式】只有一个数据，为总公司分配这M台设备所获得的最大盈利。【样例输入】32123234【样例输出】4点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态：f[i,j]代表前i个公司分配到j台设备所能获得的最大盈利方程f[i,j]=max(f[i-1,j-k]+a[i,k])0<=k<=j

点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】

点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【例题6】复制书稿问题描述：有M本书（编号为1，2，…，M），每本书都有一个页数（分别是P1，P2，…，PM）。想将每本都复制一份。将这M本书分给K个抄写员（1<=K<=M<=500)，每本书只能分配给一个抄写员进行复制。每个抄写员至少被分配到一本书，而且被分配到的书必须是连续顺序的。复制工作是同时开始进行的，并且每个抄写员复制一页书的速度都是一样的。所以，复制完所有书稿所需时间取决于分配得到最多工作的那个抄写员的复制时间。试找一个最优分配方案，使分配给每一个抄写员的页数的最大值尽可能小。（假设复制一页需要1分钟）点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【输入格式】第一行两个整数M、K；（K<=M<=100）第二行M个整数，第i个整数表示第i本书的页数。【输出格式】共1行，复制完所有书最少用的时间（分钟）【输入样例】93123456789【输出样例】17点击添加文本点击添加文本点击添加文本点击添加文本经典例题讲解【问题分析】状态f[i,j]代笔前i个人写j本书所需要的最少时间。方程：f[i,j]=min(max(f[i-1,k],s[j]-s[k]))i-1<=k<=j-1

点击添加文本点击添加文本点击添加文本点击添加文本【程序实现】

点击添加文本点击添加文本点击添加文本点击添加文本动态规划小结

求得的一个最优解当前阶段的决策仅受前一阶段决策的影响，并决定下一个阶段的决策当前阶段i多个规划(决策)当前最优决策当前非最优决策i向着目标阶段不断改变(动态)规划方向目标阶段初始阶段动态规划点击添加文本点击添加文本点击添加文本点击添加文本动态规划小结

动态规划和一般递推的