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]}


推荐相关:

动态规划模型

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


数学建模案例分析--最优化方法建模6动态规划模型举例

数学建模案例分析--最优化方法建模6动态规划模型举例_数学_自然科学_专业资料。数学...因此应当如何根据目标运 动的情况,不断地决定导弹飞行的方向和速度,使之最快...


数模国赛模型算法总结A

数模国赛模型算法总结A_理学_高等教育_教育专区。历年数模算法 模型总结,辛苦总结...网点的规 划模型研 究 电路模拟 方法在数 学建模中 的应用 奥运会网 点的...


实验四2求解动态规划模型

实验四2求解动态规划模型_数学_自然科学_专业资料。(一) 实验目的:用 WinQSB 软件求解动态规划中的背包问题及生产与存储问题。 (二) 内容与要求:求解下列两例。...


动规

动规.txt 恨一个人和爱一个人的区别是:一个放在...也就是说当前状态是前面状态的完美总结,现在与过去...这些基本模型在先面的分类中将一一介绍。 (2)三...


动画模型制作规范流程

《建筑工程管理与实务》笔记总结68份文档 新市场营销法则 助推企业成长 ...模型制作要求及制作要点 4页 1下载券 三维数字城市模型制作规... 11页 免费 ...


第​七​章​ ​动​态​规​划​方...

5.3建立动态规划数学模型... 8页 1下载券第​七​章​ ​动​态​规​划​方​法​建​模 暂无评价|0人阅读|0次下载|举报文档第...


高中物理解题常用经典模型总结

高中物理解题常用经典模型总结_理化生_高中教育_教育专区。【高中物理】高中物理解题常用经典模型总结 1、"皮带"模型:摩擦力.牛顿运动定律.功能及摩擦生热等问题. ...


优化问题与规划模型

(​非​)​线​性​规​划​、​动​态​规​划​、...优化问题与规划模型与最大、最小、最长、最短等等有关的问题都是优化问题。...


1 动态规划法模型的建立

1 动态规划模型的建立_电力/水利_工程科技_专业资料。动态规划1...应届生求职季宝典 英文个人简历模板 创意简历模板汇集 推理型题分析与总结文档...

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