动态规划的模型构建.ppt

动态规划的模型构建及其一般优化方法 长沙市雅礼中学朱全民 NOIP的动态规划试题 加分二叉树 2003 树型动态规划合唱队形 2004 线型动态规划青蛙过河 2005 线型动态规划能量项链 2006 合并类型动态规划金明的预算方案 2006 资源类型动态规划矩阵取数游戏 2007 规则类型动态规划传纸条 2008 规则类型动态规划星球贸易 2009 线型动态规划乌龟棋 2010 线型动态规划 动态规划的基本概念 阶段状态决策转移无后效性最优性原理 动态规划的时间复杂度 动态规划算法的时间复杂度 阶段数 每个阶段状态转移的状态数 每次状态转移的时间或者 状态总数 每次状态转移的时间重点 减少每个阶段的状态数 也就是减少了状态总数 编程实现 循环Fori Forj dummy 递归Solve i j Ifsolvedf i j returnf i j dummy 问题1 拦截导弹 给定N个数求最长的不上升子序列长度求最少有多少个不上升序列能覆盖所有的数 即求最少覆盖序列 N 1000 分析 设f i 表示前i个数的最长不上升序列的长度 则 f i max f j 1 其中j a i 这里0 j i n 显然时间复杂度为O n2 上述式子的含义 找到i之前的某j 这个数不比第i个数小 对于所有的j取f j 的最大值 问题2 乘积最大 设有一个长度为N的数字串 要求选手使用K个乘号将它分成K 1个部分 找出一种分法 使得这K 1个部分的乘积最大 同时 为了帮助选手能够理解题意 主持人还举了如下一个例子 有一个数字串 312 当N 3 K 1时会有两种分法 3 12 36 31 2 62这时 符合题目要求的结果是 31 2 62 现在 请你帮助你的好朋友XZ设计一个程序 求得正确的答案 分析 假设s1 si 2 i n 中插入j个 其中s1 sk中插入了j 1个 即乘式中的第j 1项为sk 1 si j k i 1 设ans i j 长度为i的数串中插入j个 的最大乘积 整型数组 显然 ans i 0 si s1对应的整型数组 ans i j max ans k j 1 sk 1 si 1 i n 1 j min i 1 m 问题3 求最长公共子序列 给定的字符序列X x0 x1 xm 1 序列Y y0 y1 yk 1 是X的子序列 存在X的一个严格递增下标序列 使得对所有的j 0 1 k 1 有xij yj 例如 X ABCBDAB Y BCDB 是X的一个子序列 给出两个字串S1和S2 长度不超过5000 求这两个串的最长公共子串长度 分析样例 S1 ABCBDAB S2 BABCBD 可以看出他们的最长公共子串有ABCB ABCD BCBD等 长度为4 从样例分析 我们思考的方式为要找出S1串与S2串的公共子串 假设将S1固定 从第1个位置开始直到最后一个位置为止 与S2的各个部分不断找最长公共子串当然S1也可以变化 这样我们即得出了思路 枚举S1的位置i枚举S2的位置j找出S1的前i位与S2的前j位的最长公共子串 直到两个串的最后一个位置为止 动态规划 设f i j 表示S的前i位与T的前j位的最长公共子串长度 则有 时间复杂度O n m 主程序框架 n length a m length b fori 1tonbeginforj 1tomdobeginf j max f j 1 pf j 从前面的状态直接转移过来 if a i b j and pf j 1 1 f j then 多增加一位的情况 f j pf j 1 1 end pf f end 说明 pf是一个与f完全相同的数组 实现f i 与f i 1 的滚动 样例运行过程 S ABCBDAB T BABCBD 初始 f i 0 0 f 0 i 0 S 1 T 1 f 1 1 MAX f 1 0 f 0 1 0 S 1 T 2 f 1 2 MAX f 1 0 1 1 S 2 T 1 f 2 1 MAX f 1 0 1 1 S 2 T 2 f 2 2 MAX f 1 2 f 2 1 1 S 2 T 3 f 2 3 MAX f 1 2 1 2 S 3 T 1 f 3 1 MAX f 3 0 f 2 1 1 S 3 T 2 f 3 2 MAX f 2 2 f 3 1 1 S 3 T 3 f 3 3 MAX f 3 2 f 2 3 2 一直求到f 8 7 ans f 8 7 1 减1是因为最后都有一个 问题4 01背包问题 有N件物品 第i件物品Wi公斤 第i件物品价值Ci元 现有一辆载重M公斤的卡车 问选取装载哪些物品 使得卡车运送的总价值最大 动态规划 可以按每个物品进行规划 同样每种物品有选和不选两种选择设F i j 表示前i件物品载重为j的最大效益 则有1 i N 0 j N初值 F 0 j 0F N M 即答案显然时间复杂度为O NM 主程序如下 fori 1tomdof 0 i 0 初始化fori 1tondof i 0 0 fori 1tondo 动态规划 递推求fforj 1tomdobeginifj w i then 背包容量够大f i j max f i 1 j w i c i f i 1 j else 背包容量不足f i j f i 1 j end 问题5 带条件的背包问题 有N件物品 第i件物品Wi公斤 第i件物品价值Ci元 第i件物品可能带0 2个附件 若装载附件 必须装载主件 反之没有约束 现有一辆载重M公斤的卡车 问选取装载哪些物品 使得卡车运送的总价值最大 分析 假设只有主件的情况 显然与经典背包问题完全相同 现在每个物品有附件 我们可以分成4种方案仅装载主件装载主件 第1个附件装载主件 第2个附件装载主件 2个附件由于上述4种并列 这是几种不同的决策同时规划即可 动态规划 设F i j 表示前i件物品背包为j的最优解 则有 1 i N 0 j M时间复杂度O NM 思考题6 系统可靠性 一个系统由若干部件串联而成 只要有一个部件故障 系统就不能正常运行 为提高系统的可靠性 每一部件都装有备用件 一旦原部件故障 备用件就自动进入系统 显然备用件越多 系统可靠性越高 但费用也越大 那么在一定总费用限制下 系统的最高可靠性等于多少 给定一些系统备用件的单价Ck 以及当用Mk个此备用件时部件的正常工作概率Pk Mk 总费用上限C 求系统可能的最高可靠性 样例 输入文件格式 第一行 nC第二行 C1P1 0 P1 1 P1 X1 0 X1 C Ck 第n行 CnPn 0 Pn 1 Pn Xn 0 Xn C Cn 输入 22030 60 650 70 750 80 850 950 70 750 80 90 95输出 0 6375 0 75 0 85 分析 设f i j 表示将j的资金用到前i项备用件中去的最大可靠性 则有F i j max F i 1 j k Cost i P i k 0 i n 0 j C 0 k jdivCost i 初始 F 0 0 1目标 F n C 时间复杂度 O k n C 这里k是常数因子 与数据相关 问题7 能量项链 在Mars星球上 每个Mars人都随身佩带着一串能量项链 在项链上有N颗能量珠 能量珠是一颗有头标记与尾标记的珠子 这些标记对应着某个正整数 对于相邻的两颗珠子 前一颗珠子的尾标记一定等于后一颗珠子的头标记 如果前一颗能量珠的头标记为m 尾标记为r 后一颗能量珠的头标记为r 尾标记为n 则聚合后释放的能量为m r n Mars单位 新产生的珠子的头标记为m 尾标记为n 显然 对于一串项链不同的聚合顺序得到的总能量是不同的 请你设计一个聚合顺序 使一串项链释放出的总能量最大 分析样例 N 4 4颗珠子的头标记与尾标记依次为 2 3 3 5 5 10 10 2 我们用记号 表示两颗珠子的聚合操作 释放总能量 4 1 2 3 10 2 3 10 3 5 10 5 10 710 动态规划 该题与石子合并完全类似 设链中的第i颗珠子头尾标记为 Si 1与Si 令F i j 表示从第i颗珠子一直合并到第j颗珠子所能产生的最大能量 则有 F i j Max F i k F k 1 j Si 1 Sk Sj i k j 边界条件 F i i 01 i k j n至于圈的处理 与石子合并方法完全相同 时间复杂度O 8n3 问题8 决斗问题 已知n个人之间的决斗的胜负情况 现在n个人围成一圈 相邻的人可以决斗 输的就挂了 然后被移走 问是否有一种决斗顺序让X最终获胜 解法 把x拆成两个点x1 x2 展开 问题转化成两个x能否相遇 从最后一步考虑 最后肯定剩下3个x1 t x2 x1到t之间的都输了 t到x2之间的都输了 现在要x1打败t或x2打败t就行了 注意这些事件发生的顺序 首先用某种顺序让x1与t相遇 然后用某准顺序让x2与t相遇 最后让x1或x2打败t 继续 用meet i j 表示i j能否相遇 如果存在一个k i k j meet i k andmeet k j true 并且i或j能击败k 注意到 i k k j 都是 i j 的子区间 也就是说对于某个区间的决策都是它的子区间 所以可以按区间长度从小到大来动规 问题9 传纸条 NOIP2008 小渊坐在矩阵的左上角 坐标 1 1 小轩坐在矩阵的右下角 坐标 m n 从小渊传到小轩的纸条只可以向下或者向右传递 从小轩传给小渊的纸条只可以向上或者向左传递 班里每个同学都可以帮他们传递 但只会帮他们一次 每个同学愿意帮忙的好感度有高有低 可以用一个0 100的自然数来表示 数越大表示越好心 小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条 即找到来回两条传递路径 使得这两条路径上同学的好心程度之和最大 现在 请你帮助小渊和小轩找到这样的两条路径 1 m n 50 贪心 很容易想到一个算法 求出1个纸条从 1 1 到 M N 的路线最大值 删除路径上的点值再求出1个纸条从 M N 到 1 1 的路线最大值 统计两次和上述算法很容易找出反例 如下图 第1次找最优值传递后 导致第2次无法传递 分析 贪心算法错误 因此我们需要同时考虑两个纸条的传递 由于小渊和小轩的路径可逆 因此 尽管出发点不同 但都可以看成同时从 1 1 出发到达 M N 点 设f i1 j1 i2 j2 表示纸条1到达 i1 j1 位置 纸条2到达 i2 j2 位置的最优值 则有 其中 i1 j1 i2 j2 1 i1 i2 M 1 j1 j2 N时间复杂度O N2M2 分析2 另一种思路 每个纸条都需要走M N步才能达到目标 因此 设F k i1 i2 表示两个纸条都走了K步 第1个纸条横坐标为i1 第2个纸条横坐标为i2的最优值 则两个纸条的纵坐标分别为j1 K i1 j2 K i2 状态转移方程如下 其中i1i21 i1 i2 M 1 k N M时间复杂度O N M M2 问题10 免费馅饼 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 分析 由于馅饼下落的时间和速度都不同 人只能向左右移动 馅饼只能向下移动 人和馅饼都同时移动 思考起来比较复杂 因此我们需要转变思路 算出每个时刻落到最底层的每个格子有多少分值的馅饼 如果将馅饼当成参照物 则馅饼向下落 可以看成馅饼不动 人往上走去摘取馅饼 这样人每1时刻都可以走到上一行的5个格子 如右图 动态规划 计算出每个格子每个时刻可能达到的馅饼分值 填入W H的天幕表 其中C i j 表示天幕的第i行第j列的馅饼分值 即第i时刻 馅饼落到最底行的馅饼分值 设F i j 表示人走到第i行j列所取得的馅饼最大分值和 则有 0 i T 1 j W 决策数为5个时间复杂度为O 5WT 问题11 加分二叉树 给定一个中序遍历为1 2 3 n的二叉树每个结点有一个权值定义二叉树的加分规则为 左子树的加分 右子树的加分 根的分数若某个树缺少左子树或右子树 规定缺少的子树加分为1 构造符合条件的二叉树该树加分最大输出其前序遍历序列 样例中序遍历为1 2 3 4 5的二叉树有很多 下图是其中的三棵 其中第三棵加分最大 为145 分析 性质 中序遍历是按 左 根 右 方式进行遍历二叉树 因此二叉树左孩子遍历序列一定在根结点的左边 右孩子遍历序列一定在根结点的右边 因此 假设二叉树的根结点为k 那么中序遍历为1 2 n的遍历序列 左孩子序列为1 2 k 1 右孩子序列为k 1 k 2 n 如下图 动态规划 设f i j 中序遍历为i i 1 j的二叉树的最大加分 则有 f i j max f i k 1 f k 1 j d k 显然f i i d i 答案为f 1 n 1 i k j n时间复杂度O n3 要构造这个树 只需记录每次的决策值 令b i j k 表示中序遍历为i i 1 j的二叉树的取最优决策时的根结点为k最后前序遍历这个树即可 问题12 聚会的快乐 你要组织一个由你公司的人参加的聚会 你希望聚会非常愉快 尽可能多地找些有趣的热闹 但是劝你不要同时邀请某个人和他的上司 因为这可能带来争吵 给定N个人 姓名 他幽默的系数 以及他上司的名字 编程找到能使幽默系数和最大的若干个人 输入 第一行一个整数N N 100 接下来有N行 每一行描述一个人的信息 信息之间用空格隔开 姓名是长度不超过20的字符串 幽默系数是在0到100之间的整数 输出 所邀请的人最大的幽默系数和 样例 样例 party inparty out58BART1HOMERHOMER2MONTGOMERYMONTGOMERY1NOBODYLISA3HOMERSMITHERS4MONTGOMERY 分析 首先 很显然公司的人员关系构成了一棵树 设f a 为a参加会议的情况下 以他为根的子树取得的最大幽默值 g a 为a不参加会议的情况下 以他为根的子树取得的最大幽默值 那么 状态转移方程就是 f a g b1 g b2 g bk d a g a max f b1 g b1 max f b2 g b2 max f bk g bk 其中b1 b2 bk为a的子结点 最后的答案就是max f root g root root是树 问题13 警卫安排 一个有N个区域的树结构上需要安排若干个警卫 每个区域安排警卫所需要的费用是不同的 每个区域的警卫都可以望见其相邻的区域 只要一个区域被一个警卫望见或者是安排有警卫 这个区域就是安全的 任务 在确保所有区域都是安全的情况下 找到安排警卫的最小费用 0 n 720 分析样例该图有6个区域如图1 安排情况如图2 红色点为安排了警卫 2号警卫可以观察1 2 5 6 3号警卫可以观察1 3 4号警卫可以观察1 4 费用 16 5 4 25 分析 对于每个点i 都有3种状态分别为 要么在父亲结点安排警卫 即被父亲看到要么在儿子结点安排警卫 即被儿子看到要么安排警卫对于ii被父亲看到 这时i没有安排警卫 i的儿子要么安排警卫 要么被它的后代看到 i被儿子看到 即i的某个儿子安排了警卫 其他儿子需要安排警卫或者被它的后代看到 i安排了警卫 i的儿子可能还需要安排警卫 这样可能有更便易的方式照顾到它的后代 所以i的儿子结点被i看到 可能安排警卫 可能被它的后代看到 动态规划 设f i 0 表示i结点被父亲看到 f i 1 表示i被它的儿子看到 f i 2 表示在i安排警卫 则状态转移方程为 时间复杂度O N2 procedurework now longint vari j sum tmp longint beginfori 1tot now dowork w now i 对每个儿子进行处理f now 0 0 以下处理now被父亲看到fori 1tot now doinc f now 0 f w now i 1 now的儿子被儿子看到sum 0 以下处理在now被儿子看到的fori 1tot now do now的儿子被儿子看到或者或安排警卫 inc sum min f w now i 1 f w now i 2 f now 1 maxlongint fori 1tot now do 枚举哪个儿子放警卫begintmp sum min f w now i 1 f w now i 2 f w now i 2 f now 1 min f now 1 tmp end f now 2 c now 以下处理在now放置警卫fori 1tot now doInc f now 2 min min f w now i 0 f w now i 1 f w now i 2 f now 1 min f now 1 f now 2 1包含了2状态 取优值 end 问题14 求最长下降序列 给出N个数 若iAj 则Ai和Aj构成了下降序列 对输入的N个数 求最长下降序列长度 例如 389 207 155 300 299 170 158 65这里最长下降序列长度为 6序列为 389 300 299 170 158 65 分析 设f i 表示前i个数的最长不上升序列的长度 则 f i max f j 1 其中ja i 这里0 j i n 显然时间复杂度为O n2 上述式子的含义 找到i之前的某j 这个数不比第i个数小 对于所有的j取f j 的最大值 优化 分析样例这里找j 是在1 i之间进行寻找 那么我们能否快速查找到我们所要更改的j呢 要能更改需要两个条件 ja i f j 尽可能大以上两个条件提示我们后面的值一定要小于等于前面的值 因此我们试着构建一个下降的序列 在这个下降的序列中查找可以更改的f值 使得序列的值尽可能大 具体过程 思考 有些同学可能会问 对于每个f 为什么只保留一个数值呢 而对于该序列 为什么要保留较大的值呢 1 再回过头来看方程 f i max f j 1 其中ja i 该式子表示找前面的一个最大f的符合条件的j 因此只要保存符合条件的最大的j就可以了 在f值相同的情况下 保留较大的数显然更好 因为后面的数若能跟较小的数构成下降序列也一定能能较大的数构成下降序列 反之则不一定 例如207与300的f 2 但207不能与299构成下降序列 而300则可以 因为生成的序列为有序序列 因此我们可以采用二分查找的方法很快查找到更新的值 时间复杂度为O n n 进一步分析 若给出一个序列 可能有多个最长下降序列 例如 9 10 8 5 6 4 3 2 1就有4个长度为7的下降序列 分别是 9 8 5 4 3 2 19 8 6 4 3 2 110 8 5 4 3 2 110 8 6 4 3 2 1给出N个数的序列 统计有种最长下降序列 分析 设t i 为前i个数中最长不下降序列的个数 则t i t j 1 j i m bj bi f i f j 1 初始为t i 1当f i n时 将t i 累加 时间复杂度为O n2 举例 a 9 10 8 5 6 4 3 2 1f 112344567t 112224444答案 f 7时 边界为 t 4 输入一个长度为 的整数序列 A1 A2 An 从中找出一段长度不超过m的连续的子序列 使得这个序列的和最大 例如 序列1 3 5 1 2 3 当M 2或3时 S 5 1 6 当M 4时 S 5 1 2 3 7 数据范围 50 的数据N M 1000100 的数据N M 20000 问题15 最大子序和 一个简化的问题 序列的最大连续和 输入一个长度为 的整数序列 A1 A2 An 从中找出一段连续的子序列 使得这个序列的和最大 和原问题相比没有M这个序列长度的限制 设F i 表示以第i个数结尾的最大连续和 以第i个数结尾的最大连续和序列 可能存在两种选择 情形一 只包含Ai情形二 包含Ai和以Ai 1结尾的最大连续和序列 状态转移方程如下 F i max Ai F i 1 Ai 边界 F 1 A1 Ans max F i 1 i n 该算法的时间复杂度为O n 分析 算法一 枚举 设F i 为以Ai结尾长度不超过M的最大子序和 对于每个F i 从1到m枚举k的值 完成Aj的累加和取最大值 该算法的时间复杂度为O n3 简化方程 用一个二叉堆来维护S i k 每次求F i 之前的操作如下 算法二 堆优化 求F i 1 时 求min S i m 1 S i 2 求F i 时 求min S i m S i 1 在堆中删除元素S i m 1 插入元素S i 1 复杂度O 2log2n 从堆中取出当前最小值 复杂度O 1 所以计算的总复杂度为O nlog2n 算法三 队列优化 在算法二中 考虑用队列来维护决策值S i k 每次只需要在队首删掉S i m 1 在队尾添加S i 1 但是取最小值操作还是需要O n 时间复杂度的扫描 考察在添加S i 1 的时候 设现在队尾的元素是S k 由于k i 1 所以S k 必然比S i 1 先出队 若此时S i 1 S k 则S k 这个决策永远不会在以后用到 可以将S k 从队尾删除掉 此时队列的尾部形成了一个类似栈的结构 队列优化 同理 若队列中两个元素S i 和S j 若i S j 则我们可以删掉S i 因为S i 永远不会被用到 此时的队列中的元素构成了一个单调递增的序列 即 S1 S2 S3 Sk 算法三 我们来整理在求F i 的时候 用队列维护S i k 所需要的操作 若当前队首元素S x 有x i m为止 若当前队尾元素S k S i 1 则S k 出队 直到S k S i 1 为止 在队尾插入S i 1 取出队列中的最小值 即队首元素 算法三 由于对于求每个F i 的时候 进队和出队的元素不止一个 但是我们可以通过分摊分析得知 每一个元素S i 只进队一次 出队一次 所以队列维护的时间复杂度是O n 而每次求F i 的时候取最小值操作的复杂度是O 1 所以这一步的总复杂度也是O n 综上所述 该算法的总复杂度是O n 问题16 理想收入问题 理想收入是指在股票交易中 以1元为本金可能获得的最高收入 并且在理想收入中允许有非整数股票买卖 已知股票在第i天每股价格是V i 元 1 i M 求M天后的理想收入 方法一 设F i 表示在第i天收盘时能达到的最高收入 则有F i 的递推关系式 公式含义 在第i天收盘时能达到的最高的收入 是将第j天收盘后的收入 全部用于买入第k天的股票 再在第i天将所持的股票全部卖出所得的收入 时间复杂度是O M3 方法二 设P i 表示前i天能获得的最多股票数 则可列出状态转移方程 设Q i 表示前i天能达到的最大收入 则可列出状态转移方程 时间复杂度是O M2 方法三 分析 上述公式的含义是当0 j i时 求Q i 1 和Q j v i v j 的最大值对于0 j i 要求Q i 实际上Q 1 Q i 1 都已经求出 因此我们只要搞一个变量保存Q j V j 的最大值即可 记为MaxQ 这样 公式可以写成 对每次求出的Q i 都更新MaxQ 时间复杂度为O M 问题17 花店橱窗布置 你有F束花 同时 你至少有同样数量的花瓶 被按顺序摆成一行 花瓶的位置是固定的 并从左至右 从1至V顺序编号 花束则可以移动 并且每束花用1至F的整数唯一标识 标识花束的整数决定了花束在花瓶中排列的顺序 即如果i j 则花束i必须放在花束j左边的花瓶中 当各个花瓶中放入不同的花束时 会产生不同的美学效果 并以美学值 一个整数 来表示 如下表 求花束的摆放取得最大的美学值 构图 假设有F束花 V个花瓶 我们将第i束花插入第j号花瓶看成一个点 i j 点 i j 具有一个权值 就是第i束花插在第j号花瓶中所产生的美学值A i j 动态规划 设P i j 表示从原点S到顶点 i j 的最长路径的长度 则 P i j Max 0 k j 1 P i 1 k A i j 1 i F 1 1 j V 1 P 0 0 0P i 0 1 i F 1 最大美学值即为P F 1 V 1 该算法的时间复杂度为O FV2 改变状态的表示 如果设Qij表示前i束花放在前j号花瓶中所得到的最大美学值 则有 Q i j Max Q i j 1 Q i 1 j 1 A i j 1 i F 1 j V Q 0 0 0Q i 0 1 i F 1 最大美学值即为Q F V 改进后的算法时间复杂度和空间复杂度都是O FV 问题描述 现有n首由RaucousRockers演唱组录制的歌曲 计划从中选择一些歌曲来发行m张唱片 每张唱片至多包含t分钟的音乐 唱片中的歌曲不能重叠 按下面的标准进行选择 1 这组唱片中的歌曲必须按照它们创作的顺序排序 2 包含歌曲的总数尽可能多 输入n m t 和n首歌曲的长度 它们按照创作顺序排序 没有一首歌超出一张唱片的长度 而且不可能将所有歌曲的放在唱片中 输出所能包含的最多的歌曲数目 问题18 RaucousRockers演唱组 设n首歌曲按照创作顺序排序后的长度为long 1 n 则动态规划的状态表示描述为 g i j k 0 i n 0 j m 0 k t 表示前i首歌曲 用j张唱片另加k分钟来录制 最多可以录制的歌曲数目 状态转移方程为 当k long i i 1时 g i j k max g i 1 j k long i 1 g i 1 j k 当k long i i 1时 g i j k max g i 1 j 1 t long i 1 g i 1 j k 规划的边界条件为 当0 j m 0 k t时 g 0 j k 0 问题的最优解为 g n m 0 算法的时间复杂度为 O n m t 改进的状态表示描述为 g i j a b 0 i n 0 j i 0 a m 0 b t 表示在前i首歌曲中选取j首录制所需的最少唱片为 a张唱片另加b分钟 状态转移方程为 g i j min g i 1 j g i 1 j 1 long i 其中 a b long i a b 的计算方法为 当b long i t时 a a b b long i 当b long i t时 a a 1 b long i 规划的边界条件 当0 i n时 g i 0 0 0 题目所求的最大值是 answer max k g n k m 1 t 算法的时间复杂度为 O n2 问题19 青蛙过河 在河上有一座独木桥 一只青蛙想沿着独木桥从河的一侧跳到另一侧 在桥上有一些石子 青蛙很讨厌踩在这些石子上 由于桥的长度和青蛙一次跳过的距离都是正整数 我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点 0 1 L 其中L是桥的长度 坐标为0的点表示桥的起点 坐标为L的点表示桥的终点 青蛙从桥的起点开始 不停的向终点方向跳跃 一次跳跃的距离是S到T之间的任意正整数 包括S T 当青蛙跳到或跳过坐标为L的点时 就算青蛙已经跳出了独木桥 题目给出独木桥的长度L 青蛙跳跃的距离范围S T 桥上石子的位置 你的任务是确定青蛙要想过河 最少需要踩到的石子数 输入文件 输入文件river in的第一行有一个正整数L 1 L 109 表示独木桥的长度 第二行有三个正整数S T M 分别表示青蛙一次跳跃的最小距离 最大距离 及桥上石子的个数 其中1 S T 10 1 M 100 第三行有M个不同的正整数分别表示这M个石子在数轴上的位置 数据保证桥的