tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

动规模型总结


1. 数字三角型 d(i,j) 表示从(i,j)出发时能得到的最大和(包括(i,j)本身的值, i 表示层 数) d(i,j) = a(i,j) + max{d(i+1,j), d(i+1,j+1)} 边界:d(i,j) = a(i,j) (i = n) 答案:d(1,1) 2. DAG (1) 最长路:嵌套矩形 d(i) 表示从结点 i 出发的最长路长度 d(i) = max{

d(j) + 1 | (i,j)∈E} 边界:d(i)无出度时 d(i) = 0 答案:max{d(i)} note:必须用递归 字典序输出 略 (2) 固定终点最长路:硬币问题 d(i)表示从结点 i 出发到结点 0 的最长路径长度 d(i) = max{d(i), d(i – v[j]) + 1 | j < n} 边界:d(0) = 0, d(i) = -INF (1 <= i <= n) 答案:d(i) 3. 城市里的间谍 d(i,j)表示时刻 i,你在车站 j(编号为 1~n),最少还需要等待多长时间。 决策 1:等 1 分钟

决策 2:搭乘向右开的车(如果有) 决策 3:搭乘向左开的车(如果有) d(i,j) = min{d(i+1, j) + 1, d(i+t[j], j+1), d(i+t[j-1], j-1)} 边界:d(T,n) = 0, d(T,i) = INF 答案:d(0,1) 4. 0-1 背包问题 (1) d(i,j)表示当前在第 i 层,背包剩余容量为 j 时接下来的最大重量和 d(i,j) = max{d(i+1, j), d(i+1, j – V(i)) + W(i)} 边界:d(i,j) = 0 (i > n) 答案:d(1,V) (2) d(i,j)表示把前 i 个物品装到容量为 j 的背包中的最大总重量 d(i,j) = max{d(i - 1, j), d(i – 1, j – V[i]) + W[i]} 滚动数组 d(i) = max{d(j), d(j – V[i]) + W[i]} note:j 逆序枚举 5. 最长上升子序列(LIS) d(i)表示以 i 结尾的最长上升子序列的长度 d(i) = max{0, d(j) | j < i, A[j] < A[i]} + 1 边界:d(1) = 1 答案:max{d(i)}

6. 最长公共子序列(LCS) d(i,j)表示 An,和 Bn 的 LCS 长度 当 A[i] = B[j]时,d(i,j) = d(i - 1, j - 1) + 1 否则,d(i,j) = max(d(i – 1, j), d(i, j - 1)) 边界:d(i,0) = d(0,j) = 1, (0 <= i, j <= n) 答案:d(i,j) 7. Lighting System Design, Uva 11400 设 s[i]为前 i 种灯泡的总数量,d[i]表示灯泡 1~i 的最小开销 d(i) = min{d(i) + (s[i] – s[j]) * c[i] + k[i] | 1 <= j < i} 边界:d(0) = 0 答案:d[n] 8. 摆花 设 d(i, j)表示前 i 种花放在前 j 个花盆里的最大方案数 d(i, j) = sum(d(i – 1, j - x)) (0 <= x <= min{a[i], j})

含义:前 j 个花盆里,第 i 种花最少放 0 个,最多放 min{a[i], j}个 边界:d(1, i) = 1 (i <= a[1]) 答案:d(n, m) 9. noip2013 花匠
花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋栋决定把 这排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大,同时,栋栋希望剩下 的花排列得比较别致。 具体而言,栋栋的花的高度可以看成一列整数 h_1, h_2, … , h_n。设当一部分花被移走后,剩下 的花的高度依次为 g_1, g_2, … , g_m,则栋栋希望下面两个条件中至少有一个满足: 条件 A:对于所有的 1<i<m/2,g_2i > g_2i-1,且 g_2i > g_2i+1; 条件 B:对于所有的 1<i<m/2,g_2i < g_2i-1,且 g_2i < g_2i+1。 注意上面两个条件在 m = 1 时同时满足,当 m > 1 时最多有一个能满足。

请问,栋栋最多能将多少株花留在原地。 数据范围及提示 对于 20%的数据,n ≤ 10; 对于 30%的数据,n ≤ 25; 对于 70%的数据,n ≤ 1000,0 ≤ h_i ≤ 1000; 对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤ h_i ≤ 1,000,000,所有的 h_i 随机生成,所有随 机数服从某区间内的均匀分布。

设令 S[i][1]表示以 i 为结尾,且降序到达 a[i]的最长抖动序列长度; 令 S[i][0]表示以 i 为结尾,且升序到达 a[i]的最长抖动序列长度。 (1)a[i+1]>a[i]: S[i+1][0]=max(S[i][1]+1,S[i][0]) S[i+1][1]=S[i][1] (2)a[i+1]<a[i]: S[i+1][0]=S[i][0] S[i+1][1]=max(S[i][0]+1,S[i][1]) (3)a[i+1]= =a[i]: S[i+1][0]=S[i][0] S[i+1][1]=S[i][1] 边界:S[1][0] = S[1][1] = 1 答案:max{S[n][0], S[n][1]}


推荐相关:

4种常见的动态规划模型

动规程序框架 function f(x,y:longint):longint; var I,j,k:longint; ...小结: 以上四种模型的动态规划, 在竞赛中应用非常广, 当然动态规划模型不仅这...


运用动态规划模型解决最短路径问题

运用动态规划模型解决最短路径问题_数学_自然科学_专业...动过程中, 所经过的距离最短(或运输的时间最少, ...=24,最优路径为 A0 由本实例我们可以总结出动态...


动态规划模型

由系统的最 后阶段向初始阶段求最优解的过程, 称为动 后阶段向初始阶段求最...数学建模Lingo求解动态规... 15页 免费 5动态规划模型 26页 2下载券 动态规划...


基于动态规划模型的生产计划安排

张金币 日期: 2012 年 04 月 04 日 题目:基于动态规划模型的生产计划安排摘要 本文针对一个周期内的足球的存储和生产等配置问题, 从储存率不变和储存 率变化...


高中物理常规考题汇总及解题方法讲解

高​中​物​理​常​规​考​题​...二是小船随着水一起运 2 动,分析时可以用平行四边...(2)竖直面内的圆周运动可以分为三个模型: ①绳...


生产与存储的动态规划模型

算​法​ ​动​态​规​划​问​题第二期(2003 年 8 月) 韶关学院学生数学建模论文集 No.2 生产与存储的动态规划模型陈立云 [摘要]:本文讨论...


数学模型动态规划

为了大规 模开发这一油田,首先必须建立相应的输运网络,使北斯洛波生产的原油能...数学模型培训讲稿4--动态... 129页 3下载券 数学建模 课件 第6章:动... ...


动态规划与最优控制模型

第四章 最优控制模型 (管理,决策方面应用,因此可说管理决策模型) §1 §1....上次这种动态规 划的办法: 是将把一个四阶段决策问题化为四个互相嵌入子问题,...


电源规划

一、电源规划的主要特点 以电源建设投入费用最少为目标函数形成的数学模型称为电源优化模型。 此时, 电源规 划需对以下问题作出定量分析。 1.方案的投资流及逐年...


生产与库存的动态规划模型

数学模型 一、学生自我总结 通过这次课程设计,让我...得到一个简单的线性规模型: Min z = ∑ x k +...基于多阶段决策的库存动... 暂无评价 2页 ¥1....

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com