动态规划的模型构建.ppt

动态规划的模型构建及其一般优化方法NOIP的动态规划试题引例：数字三角形动态规划的基本概念动态规划的基本概念最优化原理无后效性动态规划的解题步骤编程实现？数字三角形求解问题1：求最短距离（1）分析问题1：求最短距离（2）分析思考？分析问题2:求最长公共子序列动态规划思考？问题3：01背包问题动态规划思考？问题4：石子合并示例N=5石子数分别为346542。动态规划思考题：多边形样例问题5：Robots举例分析：状态转移方程思考？问题6：加分二叉树样例
中序遍历为1,2,3,4,5的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为145.分析动态规划思考题：选课输入
输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1≤M≤1000)，N表示学生可以选的课程总数（1≤N≤M)。
以下M行每行代表一门课，课号依次为1，2……M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。
输出
输出文件第一行只有一个数，即实际所选课程的学分总数。以下N行每行有一个数，表示学生所选课程的课号。
问题7：聚会的快乐样例分析思考题：警卫安排动态规划的优化问题8：求最长下降序列分析优化具体过程：
思考？进一步分析分析输入一个长度为ｎ的整数序列（A1,A2,……,An），从中找出一段长度不超过m的连续的子序列，使得这个序列的和最大。
例如：序列1，-3，5，1，-2，3一个简化的问题
算法一——枚举简化方程用一个二叉堆来维护S(i-k)，每次求F(i)之前的操作如下：算法三：队列优化队列优化算法三算法三问题10：理想收入问题方法一方法二方法三问题11：青蛙过河【输入文件】
输入文件river.in的第一行有一个正整数L（1<=L<=109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1<=S<=T<=10，1<=M<=100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
【输出文件】
输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。
【样例输入】
10
235
23567
【样例输出】
2
【数据规模】
对于30%的数据，L<=10000；
对于全部的数据，L<=109。分析进一步分析于是我们可以分两种情况讨论：
1.S=T时：
这时候由于每一步只能按固定步长跳，所以若第i个位置上有石子并且imodS=0那么这个石子就一定要被踩到。这是我们只需要统计石子的位置中哪些是S的倍数即可。复杂度O(M)
2.S<T时：
首先我们作如下处理：若存在某两个相邻石子之间的空白区域长度>MaxK+2*T，我们就将这段区域缩短成长度为MaxK+2*T。可以证明处理之后的最优值和原先的最优值相同。 所以原来的最优解必然在处理之后的最优解解集中。
经过这样的压缩处理，独木桥的长度L’最多为(M+1)*(MaxK+2*T)+M，大约12000左右。压缩之后再用先前的动态规划求解，复杂度就简化成了O(L’*(T-S))，已经可以在时限内出解了。
这样本题就得到了解决。