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



推荐相关:

动态规划阶段总结之基础篇[必看]

动​态​规​划​阶​段​总​结​之​基​础​篇​[...[小结]本文简单的介绍了动态规划中最基本也是最常用的 6 个模型, 细心的读者...


数学模型动态规划

为了大规 模开发这一油田,首先必须建立相应的输运...建立动态规划模型是十分重要的. 其步骤可归纳如下:...已知用于第 i 项活 动的资源数为 x i 时,可以...


动画模型规范_图文

动画模型规范_机械/仪表_工程科技_专业资料。模型规范 上海丝路动画部模型制作规范 一.接项目 1.由动画部经理或者模型主管来安排模型项目负责人 2.模型项目负责人...


数学规划模型

3.3 本章小结本章主要介绍了数学规划模型在实践中的实例生产模型和设备更新问题...分析 20 1 2 课程设计质量 问题思路清晰,结构严谨,文理通顺,撰写规 范,图表...


优化问题与规划模型

参见线性规 划书籍 将实际问题归结为线性规划模型是一个探索创造的过程。 线性规划模型的求解仍是计算数学的一个难题。 例 2 供货问题 一家公司生产某种商品. ...


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

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


线性规划模型的应用与灵敏度分析

线性规划模型的应用与灵敏度分析_数学_自然科学_专业...之后,线性规 划理论逐步趋于成熟,在实用中日益广泛...2.3 单纯形法的求解过程小结 2.3.1 人造基、...


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

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


零件加工时间最优化的动态规划模型

零件加工时间最优的动态规划模型 摘要 零件加工最有时间问题是典型的动态规划问题...资源分配的多目标优化动... 3页 2下载券 基于零件加工问题的0-1规... 20...


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

运用动态规划模型解决物流配送中的最短 路径问题摘要...动过程中, 所经过的距离最短(或运输的时间最少, ...A7 ? A6 ? A9 由本实例我们可以总结出动态规划的...

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