搜索
动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程最优化的数学方法。动态规划算法把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，以得到全局最优策略。动态规划是信息学竞赛中选手必须熟练掌握的一种算法,它以其多元性广受出题者的喜爱。近年来，动态规划几乎每次都出现在NOIp的赛场上，而且还有越来越多的趋势。因此，掌握基本的NOIp动态规划题是至关重要的。动态规划实质：枚举+递推状态状态转移方程SampleProblem113591从树的根到树的叶节点，最多能取多少数？贪心：答案错误暴力搜索：如果数据大会超时我们先将NOIp里的动态规划分分类：最长不降子序列背包方格取数石子归并状态压缩数学递推顺序递推设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)a(j)(i，j=n)例如3，18，7，14，10，12，23，41，16，24。若存在i1i2i3…ie且有a(i1)a(i2)…a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。最长的不下降序列就是求长度最长的子序列。Fori:=1TonDoForj:=1Toi-1DoIf(a[i]=a[j])And(f[i]f[j]+1)Thenf[i]:=f[j]+1;合唱队形（NOIp2004）【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1...TiTi+1…TK(1=i=K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【输入文件】输入文件第一行是一个整数N(2=N=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130=Ti=230)是第i位同学的身高。【输出文件】输出文件包括一行，这一行只包含一个整数，就是最少需要几位同学出列。SampleProblem2拦截导弹（NOIp1999）某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。样例：INPUTOUTPUT389207155300299170158656（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）SampleProblem3反例：9871106549871106549871106541101101010987110654987110654106541065401背包：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。完全背包：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。Fori:=1TonDoForj:=MaxDowntoa[i]Do(a[i]ToMax)Iff[j]f[j-a[i]]+b[i]Thenf[j]:=f[j-a[i]]+b[i];SampleProblem4金明的预算方案（NOIp2006）【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的。如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。SampleProblem4【输入文件】第1行，为两个正整数Nm（其中N（32000）表示总钱数，m（60）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数vpq（其中v表示该物品的价格（v10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q0，表示该物品为附件，q是所属主件的编号）【输出文件】只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值。【输入样例】100058002040051300514003050020【输出样例】2200Fori:=1TonDoForj:=mDowntoa[i]DoIff[j-a[i]]-1thenBegin00Iff[j-a[i]]+b[i]f[j]Thenf[j]:=f[j-a[i]]+b[i];Ff:=f[j-a[i]]+b[i];01Ifj+s[i,1,1]=mThenIfFf+s[i,1,2]f[j+s[i,1,1]]Thenf[j+s[i,1,1]]:=Ff+s[i,1,2];10Ifj+s[i,2,1]=mThenIfFf+s[i,2,2]f[j+s[i,2,1]]Thenf[j+s[i,2,1]]:=Ff+s[i,2,2];11Ifj+s[i,1,1]+s[i,2,1]=mThenIfFf+s[i,1,2]+s[i,2,2]f[j+s[i,1,1]+s[i,2,1]]Thenf[j+s[i,1,1]+s[i,2,1]]:=Ff+s[i,1,2]+s[i,2,2];End;End;SampleProblem5邮票面值设计（NOIp1999）给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1～MAX之间的每一个邮资值都能得到。例如，N=3，K=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。【样例】INPUTN=3K=2OUTPUT13MAX=7如果你一看到这道题目就想到搜索，那么这道题目就是搜索。那么为什么它出现在动态规划的专题中的？是因为……你DFS生成一组邮票面值之后，你需要用某种方法把它能达到的面额都枚举出来。而这个工作如果要让枚Cnm举来做，那么太浪费资源了。枚举的复杂度是，尽管n、m很小，但是在大DFS的前提下就不怎么划算了。因此我们使用DP来枚举出所有可能的面额，而方法，就是传说中的完全背包（经过处理的）。SampleProblem6方格取数（NOIp2000）设有N*N的方格图(N=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。13+14+4+21+15=67一取方格数：f[i,j]:=max{f[i-1,j],f[i,j-1]};现在要做的数二取方格数，是否还能像一取方格数那样如法炮制呢？答案是肯定的！我们观察一下它的路径。f[i,j]是从f[i-1,j]或者f[i,j-1]走来。无论是从f[i-1,j]还是f[i,j-1]走来，要么是x坐标+1，要么是y坐标+1，总归x坐标的值+y坐标的值一定比前一个多1。我们来验证一下：XYZX坐标（3，3）3+3=6Y坐标（3，4）3+4=7Z坐标（4，4）4+4=8X、Y、Z的坐标和在不断增加，每次+1。再观察，我们发现，走第n步时，能走到点是固定的。观察其坐标我们发现，第n步能走到的点其坐标和为n-1。因此，走到第n步时，x坐标和y坐标的和就知道=n+1，这样我们就不必同时知道2条路线x坐标和y坐标了，知道其中一个t，另外一个就可以用n+1-t来表示了。用f[x,i,j]表示走到第x步时，第1条路线走到横坐标为i的地方，第2条路线走到了横坐标为j的地方。这样，我们只要枚举x，i，j，就能递推出来了。Forx:=3Tom+nDoFori:=1ToMin(x,n)DoForj:=1ToMin(x,n)DoBeginf[x,i,j]:=Max(f[x-1,i,j],f[x-1,i-1,j],f[x-1,i,j-1],f[x-1,i-1,j-1]);Ifi=jThenInc(f[x,i,j],a[i,x-i])ElseBeginInc(f[x,i,j],a[x-i,i]);Inc(f[x,i,j],a[x-j,j]);End;End;同样三取方格数只要f[x,i,j,k]用同样的方法即可。传纸条（NOIp2008）【问题描述】小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。SampleProblem7SampleProblem8石子归并原题【题目描述】在一个圆形操场的四周摆放着N堆石子(N=100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(=20).选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小。【输入数据】第一行为石子堆数N;第二行为每堆的石子数,每两个数之间用一个空格分隔。【输出数据】一行，最小总和。【输入】44594【输出】224594598总和：8913总和：2122总和：43我们用f[i,j]表示以i堆石子为开头，以j堆石子为结尾的一系列石子归并起来的最小总和。因为题目中说，只能归并相邻的两堆石子。