搜索
NOIP的动态规划试题•加分二叉树(2003)—树型动态规划•合唱队形(2004)—线型动态规划•青蛙过河(2005)—线型动态规划•能量项链(2006)—合并类型动态规划•金明的预算方案(2006)—资源类型动态规划•矩阵取数游戏(2007)—规则类型动态规划•传纸条(2008)—规则类型动态规划•星球贸易(2009)—线型动态规划•乌龟棋(2010)—线型动态规划引例：数字三角形如图所示的数字三角形中•从第一行的数字出发•每次向左下或右下走一格，直到最后一行•要求沿途数字之和最大132410143220动态规划的基本概念•阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。•状态：某一阶段的出发位置称为状态。通常一个阶段包含若干状态。•决策：从某阶段的一个状态演变到下一个阶段某状态的选择。•策略：由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。动态规划的基本概念•状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。•目标函数与最优化概念：目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。最优化原理•一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。•简而言之，一个最优化策略的子策略总是最优的。•最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。无后效性•“过去的步骤只能通过当前状态影响未来的发展，当前的状态是历史的总结”。这条特征说明动态规划只适用于解决当前决策与过去状态无关的问题。状态，出现在策略任何一个位置，它的地位相同，都可实施同样策略，这就是无后效性的内涵。•举例•最短路（不带负权边，带负权边）动态规划的解题步骤•划分阶段：注意阶段一定要是有序的或者是可排序的，否则问题就无法求解。•选择状态：状态的选择要满足无后效性。•确定决策：决策决定着状态的转移，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。•写出状态转移方程（包括边界条件和取值范围）：根据问题的性质（求最大/最小），用数学方程描述状态转移的方法和过程编程实现？•循环–Fori…–Forj…–(dummy)•递归–Solve(i,j)–Ifsolvedf[i][j]returnf[i][j]–(dummy)数字三角形求解•状态：f(i,j)表示走到第i行j列获得的最大值•状态转移方程:f(i,j)=max{f(i-1,j),f(i-1,j+1)}+a[i,j]初始：f(0,0)=0问题1：求最短距离（1）•某人要从S1前往SN，其中Si至Si+1有若干种行进方式（步行，自行车，公交车，越野车，etc），分别要花费一定的时间•问最快到达的时间是多少？分析•划分阶段、选择状态：•到达各个不同的地点作为一个阶段•一个阶段里就一个状态•用F[i]表示从S1到达Si所需最短的时间•写出规划方程（包括边界条件）：•F[1]=0•F[i]=F[i-1]+Si-1到达Si所需花费的最短时间问题1：求最短距离（2）•某人要从S1前往SN，其中Si至Si+1有若干种行进方式（步行，自行车，公交车，越野车，etc），分别要花费一定的时间，并且如果在一个地点选择切换行进方式，需要额外消耗一定的时间。•问最快到达的时间是多少？分析•划分阶段、选择状态：•使用与上面一样的方案发现不可行，无法解决判定是否需要切换行进方式•加一维状态进行表示•用f[i][j]表示要从S1到达Si，在Si时使用的出行方式为j，所需最短的时间•写出规划方程（包括边界条件）思考？•必须在每个地点切换行进方式？•“Si至Si+1有若干种行进方式”为“Si至Sj(ji)有若干种行进方式”？•若为任意两点Si至Sj之间都有若干种行进方式？•若在切换时候需要行进方式时须增加时间？•中途经过的地点不能超过X个，该如何处理？•若费用为负怎么办？分析•设f(i)表示前i个数的最长不上升序列的长度。则,f(i)=max{f(j)+1},其中jianda[j]=a[i]这里0ji=n。显然时间复杂度为O(n2)。•上述式子的含义：找到i之前的某j，这个数不比第i个数小,对于所有的j取f(j)的最大值。问题2:求最长公共子序列•给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列i0，i1，…，ik-1，使得对所有的j=0，1，…，k-1，有xij=yj。•例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。•给出两个字串S1和S2，长度不超过5000.•求这两个串的最长公共子序列长度。动态规划•设f(i,j)表示S的前i位与T的前j位的最长公共子串长度。则有，•时间复杂度O(n*m)jijitsjijiftsjijifjifjijif&&0,,1)1,1(&&0,)},,1(),1,(max{0||0,0),(当当当思考？•给出两个串，求最长公共子串？•给定两个字符串，求最小编辑次数使得两个字符串相等，所谓编辑，即删除、插入或修改某个字符。•给出一个串，求最小编辑次数，使得某个串变成回文串？问题3：01背包问题•有N件物品;•第i件物品Wi公斤;•第i件物品价值Ci元;•现有一辆载重M公斤的卡车;•问选取装载哪些物品，使得卡车运送的总价值最大？动态规划•可以按每个物品进行规划，同样每种物品有选和不选两种选择•设F(i,j)表示前i件物品载重为j的最大效益，则有•1=i=N,0=j=N•初值：F(0,j)=0•F(N,M)即答案•显然时间复杂度为O(NM)种物品不装载第种物品装载第ijiFiiCiwjiFMaxjiF),,1(],[])[,1(),(思考？•完全背包问题：即每个物品可取无限次。•多重背包问题：第i种物品可取n[i]次。•带条件背包问题：取某种物品，必须取另外一种物品的限制。•二维背包问题：物品分为两类，每类分别放到一个背包中。•每个物品有个编号，价值最大的前提下，所取物品组成的排列字典序最小。问题4：石子合并•在一园形操场四周摆放N堆石子(N≤100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(≤20),(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少(2)选择一种合并石子的方案,使得做N-1次合并,得分的总和最大•输入数据:第一行为石子堆数N;第二行为每堆石子数,每两个数之间用一空格分隔.•输出数据:从第1至第N行为得分最小的合并方案.第N+1行为空行.从N+2到2N+1行是得分最大的合并方案.示例N=5石子数分别为346542。用贪心法的合并过程如下：第一次346542得分5第二次54654得分9第三次9654得分9第四次969得分15第五次159得分24第六次24总分：62然而仔细琢磨后，发现更好的方案：第一次346542得分7第二次76542得分13第三次13542得分6第四次1356得分11第五次1311得分24第六次24总分：61显然，贪心法是错误的。动态规划•用data[i,j]表示将从第i颗石子开始的接下来j颗石子合并所得的分值，•max[i,j]表示将从第i颗石子开始的接下来j颗石子合并可能的最大值，那么：max[i,j]=max(max[i,k]+max[i+k,j–k]+data[i,k]+data[i+k,j–k])(2=k=j)max[i,i]=0•同样的，我们用min[i,j]表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值，可以得到类似的方程：•min[i,j]=min(min[i,k]+min[i+k,j–k]+data[i,k]+data[i+k,j–k])(0=k=j)•min[i,i]=0•这样，我们完美地解决了这道题。时间复杂度也是O(n3)。思考题：多边形•多角形是一个单人玩的游戏，开始时有一个N个顶点的多边形。如图，这里N=4。每个顶点有一个整数标记，每条边上有一个“+”号或“*”号。边从1编号到N。第一步，一条边被拿走；随后各步包括如下：•选择一条边E和连接着E的两个顶点V1和V2；•得到一个新的顶点，标记为V1与V2通过边E上的运算符运算的结果。•最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。-7425+*1234+*样例-7425+*124+42+*24-24+2-40写一个程序，对于给定一个多边形，计算出可能的最高得分，并且列出得到这个分数的过程。问题5：Robots•在一个n*m的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。•问：最多能拾多少垃圾。在最多的情况下，有多少种方案？请举出一种方案来。•数据范围:n=100,m=100举例•最多能拾5块。有4种方法。分析：•因为只能向右或者向下走。也就是说不能走回头路。于是考虑动态规划。•设F[i,j]表示从(1,1)点开始走到(i,j)的时候，最多捡了多少垃圾。G[i,j]表示在f[i,j]最大的时候，有多少种方案。C[i,j]=1表示(i,j)点有垃圾。C[i,j]=0表示没有。状态转移方程•根据(i,j)只能从(i-1,j)或者(i,j-1)走过来。•于是f[i,j]=Max{f[i-1,j],f[i,j-1]}+c[i,j].•怎么求g(i,j)？•可变成有向无环图来解决。思考？•两个机器人同时捡垃圾，如何处理？•三个机器人呢？•若某些垃圾之间有联系，必须同时拾捡？免费馅饼•SERKOI最新推出了一种叫做“免费馅饼”的游戏。•游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘。•游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。•馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。•写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。•输入数据：第一行:宽度W（1~99奇数）和高度H（1~100整数）接下来给出了一块馅饼信息。由4个正整数组成，分别表示了馅饼的初始下落时刻、水平位置、下落速度、分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。•输出数据：收集到的馅饼最大分数之和。•由上图可知，尽管下落了4个馅饼，但只能接到3个：•第1时刻可以接到分值为5的馅饼•第2时刻可以接到分值为3的馅饼•第3时刻可以接到分值为4的馅饼•因此馅饼的总分值为5+3+4=12问题6：加分二叉树•给定一个中序遍历为1,2,3,…,n的二叉树•每个结点有一个权值•定义二叉树的加分规则为：–左子树的加分×右子树的加分＋根的分数–若某个树缺少左子树或右子树，规定缺少的子树加分为1。•构造符合条件的二叉树–该树加分最大–输出其前序遍历序列•样例•中序遍历为1,2,3,4,5的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为145.分析•性质：中序遍历是按“左-根-右”方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！•因此，假设二叉树的根结点为k，那么中序遍历为1,2,…,n的遍历序列，左孩子序列为1,2,…,k-1，右孩子序列为k+1,k+2,…,n，如下图动态规