动态规划47题

动态规划练习 1 动态规划练习 题目一览 第一题第二题第三题第四题第五题 题目名称总分邮票家的范围游戏商店购物 提交文件 inflatestampsrangegameshopping 第六题第七题第八题第九题第十题 题目名称 破锣摇滚 乐 队 麦香牛块最长前缀货币系统垃圾陷阱 提交文件 rockersnuggetsprefixmoneywell 第十一题第十二题第十三题第十四题第十五题 题目名称神秘的咒语天堂的馈赠上帝的爱好苹果旅游文科生的悲哀 提交文件 cursepresentliketraveldole 第十六题第十七题第十八题第十九题第二十题 题目名称硬件糖果盒能量项链金明的预算方案潜水员 提交文件 hardwarecandyenergybudgetgas 第二十一题第二十二题第二十三题第二十四题第二十五题 题目名称观光游览任务安排筷子递增序列 power 提交文件 viewbatchchopincsqpower 第二十六题第二十七题第二十八题第二十九题第三十题 题目名称清扫破译密码奶牛家谱集合书本整理 提交文件 stablespasswordnocowssubsetbook 第三十一题第三十二题第三十三题第三十四题第三十五题 题目名称城堡简单的网络游戏佳佳的魔杖编码将功补过 提交文件 castlesimple mwand codesinform 第三十六题第三十七题第三十八题第三十九题第四十题 题目名称质数取石子多人背包不听话的机器人路灯的改建计划吃西瓜 提交文件 pgamebagsrobotlightmatrix 第四十一题第四十二题第四十三题第四十四题第四十五题 题目名称给 MM 的生日礼物最勇敢的机器人创意吃鱼法爱心蜗牛工作 提交文件 giftbravestmealbadnewsWork 第四十六题第四十七题 题目名称最大矩形座位安排 动态规划练习 2 提交文件 maxmatrixseat 总分 问题描述 学生在我们 USACO 的竞赛中的得分越多我们越高兴 我们试着设计我们的竞赛以便人们能尽可能的 多得分 这需要你的帮助 我们可以从几个种类中选取竞赛的题目 这里的一个 种类 是指一个竞赛题目的集合 解决集合 中的题目需要相同多的时间并且能得到相同的分数 你的任务是写一个程序来告诉 USACO 的职员 应该 从每一个种类中选取多少题目 使得解决题目的总耗时在竞赛规定的时间里并且总分最大 输入包括竞 赛的时间 M 1 M 10000 不要担心 你要到了训练营中才会有长时间的比赛 和 种类 的数目 N 1 N 10000 后面的每一行将包括两个整数来描述一个 种类 第一个整数说明解决这种题目能得的分数 1 points 10000 第二整数说明解决这种题目所需的 时间 1 minutes 10000 你的程序应该确定我们应该从每个 种类 中选多少道题目使得能在竞赛 的时间中得到最大的分数 来自任意的 种类 的题目数目可能任何非负数 0 或更多 计算可能得到的最大分数 输入格式 输入文件中的第 1 行 M N 竞赛的时间和题目 种类 的数目 第 2 N 1 行 两个整数 每个 种类 题目的分数和耗时 输出格式 输出文件中仅一行 包括那个在给定的限制里可能得到的最大的分数 输入输出样例 输入 300 4 100 60 250 120 120 100 35 20 输出 605 从第 2 个 种类 中选两题第 4 个 种类 中选三题 动态规划练习 3 邮票 问题描述 已知一个 N 枚邮票的面值集合 如 1 分 3 分 和一个上限 K 表示信封上能够贴 K 张邮票 计算从 1 到 M 的最大连续可贴出的邮资 例如 假设有 1 分和 3 分的邮票 你最多可以贴 5 张邮票 很容易贴出 1 到 5 分的邮资 用 1 分邮 票贴就行了 接下来的邮资也不难 6 3 3 7 3 3 1 8 3 3 1 1 9 3 3 3 10 3 3 3 1 11 3 3 3 1 1 12 3 3 3 3 13 3 3 3 3 1 然而 使用 5 枚 1 分或者 3 分的邮票根本不可能贴出 14 分的邮资 因此 对于这两种邮票的集合和 上限 K 5 答案是 M 13 输入格式 输入文件中的第一行 两个整数 K 和 N 1 K 200 1 N 50 K 是可用的邮票总数 N 是邮票面 值的数量 第二行 文件末 N 个整数 每行 15 个 列出所有的 N 个邮票的面值 面值不超过 10000 输出格式 输出文件中的第一行 一个整数 从 1 分开始连续的可用集合中不多于 K 张邮票贴出的邮资数 输入输出样例 输入 5 2 1 3 输出 13 动态规划练习 4 家的范围 问题描述 农民约翰在一片边长是 N 2 N2 2 的个数 当然 放牧区 域可能是重叠 输入格式 输入文件中的第 1 行 N 牧区的边长 第 2 到 n 1 行 N 个没有空格分开的字符 0 表示 那一个区段被毁坏了 1 表示 准备好被吃 输出格式 输出那些存在的正方形的大小和个数 一种一行 输入输出样例 输入 6 101111 001111 111111 001111 101101 111001 输出 2 10 3 4 4 1 动态规划练习 5 游戏 问题描述 有如下一个双人游戏 N 2 N 100 个正整数的序列放在一个游戏平台上 两人轮流从序列的两 端取数 取数后该数字被去掉并累加到本玩家的得分中 当数取尽时 游戏结束 以最终得分多者为胜 编写一个执行最优策略的程序 最优策略就是使自己能得到在当前情况下最大的可能的总分的策略 你的程序要始终为第二位玩家执行最优策略 输入格式 输入文件中的第一行 正整数 N 表示序列中正整数的个数 第二行至末尾 用空格分隔的 N 个正整数 大小为 1 200 输出格式 输出文件中只有一行 用空格分隔的两个整数 依次为玩家一和玩家二最终的得分 输入输出样例 输入 6 4 7 2 9 5 2 输出 18 11 动态规划练习 6 商店购物 问题描述 在商店中 每一种商品都有一个价格 用整数表示 例如 一朵花的价格是 2 zorkmids z 而一 个花瓶的价格是 5z 为了吸引更多的顾客 商店举行了促销活动 促销活动把一个或多个商品组合起来降价销售 例如 三朵花的价格是 5z 而不是 6z 两个花瓶和一朵花的价格是 10z 而不是 12z 编写一个程序 计算顾 客购买一定商品的花费 尽量利用优惠使花费最少 尽管有时候添加其他商品可以获得更少的花费 但 是你不能这么做 对于上面的商品信息 购买三朵花和两个花瓶的最少花费是 以优惠价购买两个花瓶和一朵花 10z 以原价购买两朵花 4z 输入格式 输入文件中包括一些商店提供的优惠信息 接着是购物清单 第一行 优惠商品的种类数 s 0 s 99 第二行 第 s 1 行 每一行都用几个整数来表示一种优惠方式 第一个整数 n 1 n 5 表示这种 优惠方式由 n 种商品组成 后面 n 对整数 c 和 k 1 k 5 1 c 999 表示 k 个编号为 c 的商品共同 构成这种优惠 最后的整数 p 1 p 9999 表示这种优惠的优惠价 优惠价总是比原价低 第 s 2 行 这一行有一个整数 b 0 b 5 表示需要购买 b 种不同的商品 第 s 3 行 第 s b 2 行 这 b 行中的每一行包括三个整数 c k 和 p 1 c 999 1 k 5 1 p 999 c 表示唯一的商品编号 k 表示需要购买的 c 商品的数量 p 表示 c 商品的原价 最多购买 5 5 25 个商品 输出格式 输出文件中只有一行 输出一个整数 购买这些物品的最低价格 输入输出样例 输入 2 1 7 3 5 2 7 1 8 2 10 2 7 3 2 8 2 5 输出 14 动态规划练习 7 破锣摇滚 乐队 问题描述 你刚刚继承了流行的 破锣摇滚 乐队录制的尚未发表的 N 首歌的版权 你打算从中精选一些歌曲 发行 M 张 CD 每一张 CD 最多可以容纳 T 分钟的音乐 一首歌不能分装在两张 CD 中 不巧你是一位古典音乐迷 不懂如何判定这些歌的艺术价值 于是你决定根据以下标准进行选择 歌曲必须按照创作的时间顺序在 CD 盘上出现 选中的歌曲数目尽可能地多 输入格式 输入文件中的第一行 三个整数 N T M 1 N 20 1 M 20 1 T 20 第二行 N 个整数 分别表示每首歌的长度 按创作时间顺序排列 输出格式 一个整数 表示可以装进 M 张 CD 盘的乐曲的最大数目 输入输出样例 输入 4 5 2 4 3 4 2 输出 3 动态规划练习 8 麦香牛块 问题描述 农夫布朗的奶牛们正在进行斗争 因为它们听说麦当劳正在考虑引进一种新产品 麦香牛块 奶牛 们正在想尽一切办法让这种可怕的设想泡汤 奶牛们进行斗争的策略之一是 劣质的包装 看 奶牛 们说 如果你用只有一次能装 3 块 6 块或 10 块的三种包装盒装麦香牛块 你就不可能满足想要一次只 想买 1 2 4 5 7 8 11 14 或 17 块麦香牛块的顾客了 劣质的包装意味着劣质的产品 你的任务是帮助这些奶牛 给出包装盒的种类数 N 1 N 10 和 N 个代表不同种类包装盒容纳麦香 牛块个数的正整数 i 1 i 256 输出顾客不能用上述包装盒 每种盒子数量无限 买到麦香牛块的最 大块数 如果在限定范围内所有购买方案都能得到满足 则输出 0 范围限制是所有不超过 2000000000 的正整数 输入格式 输入文件中的第 1 行 包装盒的种类数 N 第 2 行到 N 1 行 每个种类包装盒容纳麦香牛块的个数 输出格式 输出文件中只有一行数字 顾客不能用包装盒买到麦香牛块的最大块数或 0 如果在限定范围内所有 购买方案都能得到满足 输入输出样例 输入 3 3 6 10 输出 17 动态规划练习 9 最长前缀 问题描述 在生物学中 一些生物的结构是用包含其要素的大写字母序列来表示的 生物学家对于把长的序列 分解成较短的 称之为元素的 序列很感兴趣 如果一个集合 P 中的元素可以通过串联 允许重复 串联 相当于 Pascal 中的 运算符 组成 一个序列 S 那么我们认为序列 S 可以分解为 P 中的元素 并不是所有的元素都必须出现 举个例子 序 列 ABABACABAAB 可以分解为下面集合中的元素 A AB BA CA BBC 序列 S 的前面 K 个字符称作 S 中长度为 K 的前缀 设计一个程序 输入一个元素集合以及一个大写 字母序列 计算这个序列最长的前缀的长度 输入格式 输入文件中的开头包括 1 200 个元素 长度为 1 10 组成的集合 用连续的以空格分开的字符串 表示 字母全部是大写 数据可能不止一行 元素集合结束的标志是一个只包含一个 的行 集合中 的元素没有重复 接着是大写字母序列 S 长度为 1 200000 用一行或者多行的字符串来表示 每行不 超过 76 个字符 换行符并不是序列 S 的一部分 输出格式 输出文件中只有一行 输出一个整数 表示 S 能够分解成 P 中元素的最长前缀的长度 输入输出样例 输入 A AB BA CA BBC ABABACABAABC 输出 11 动态规划练习 10 货币系统 问题描述 母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统 In their own rebellious way 他们对货币的数值感到好奇 传统地 一个货币系统是由 1 5 10 20 或 25 50 和 100 的单位 面值组成的 母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值 举例来说 使用一 个货币系统 1 2 5 10 产生 18 单位面值的一些可能的方法是 18 1 9 2 8 2 2 1 3 5 2 1 等等其它 编写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值 保证总数将会适合 long long C C 和 Int64 Free Pascal 输入格式 货币系统中货币的种类数目是 V 1 V 25 要构造的数量钱是 N 1 N 10000 第 1 行 两个整数 V 和 N 第 2 V 1 行 可用的货币 V 个整数 每行一个 每行没有其它的数 输出格式 输出文件中单独的一行包含那个可能的构造的方案数 输入输出样例 输入 3 10 1 2 5 输出 10 动态规划练习 11 垃圾陷阱 问题描述 卡门 农夫约翰极其珍视的一条 Holsteins 奶牛 已经落了到 垃圾井 中 垃圾井 是农夫 们扔垃圾的地方 它的深度为 D 2 D 100 英尺 卡门想把垃圾堆起来 等到堆得与井同样高时 她就能逃出井外了 另外 卡门可以通过吃一些垃 圾来维持自己的生命 每个垃圾都可以用来吃或堆放 并且堆放垃圾不用花费卡门的时间 假设卡门预先知道了每个垃圾扔下的时间 t 0 t 1000 以及每个垃圾堆放的高度 h 1 h 25 和吃进该垃圾能维持生命的时间 f 1 f 30 要求出卡门最早能逃出井外的时间 假设卡门当前体内 有足够持续 10 小时的能量 如果卡门 10 小时内没有进食 卡门就将饿死 输入格式 输入文件中的第一行为两个整数 D 和 G 1 G 100 G 为被投入井的垃圾的数量 第二到第 G 1 行每行包括三个整数 T 0 T 1000 表示垃圾被投进井中的时间 F 1 F 30 表示该垃圾能维持卡门生命的时间 H 1 H 25 该垃圾能垫高的高度 输出格式 如果卡门可以爬出陷阱 输出一个整表示最早什么时候可以爬出 否则输出卡门最长可以存活多长 时间 输入输出样例 输入 20 4 5 4 9 9 3 2 12 6 10 13 1 1 输出 13 样例说明 卡门堆放她收到的第一个垃圾 height 9 卡门吃掉她收到的第二个垃圾 使她的生命从 10 小时延伸到 13 小时 卡门堆放第三个垃圾 height 19 卡门堆放第四个垃圾 height 20 动态规划练习 12 神秘的咒语 问题描述 身为拜月教的高级间谍 你的任务总是逼迫你出生入死 比如这一次 拜月教主就派你跟踪赵灵儿 一行 潜入试炼窟底 据说试炼窟底藏着五行法术的最高法术 风神 雷神 雪妖 火神 山神的咒语 为了习得这些法 术 要付出艰辛的努力 但是回报同样十分丰厚 拜月希望你告诉他咒语的长度为多少 你 请问您想知道咒语的具体内容吗 拜月 想 但 是 vijos 不支持 special judge 原来大人物也有大人物的悲哀 于是你偷偷躲在一边 想乘机看看咒语究竟是什么 突然 天空 试炼窟底看的到天空 出现了两条非常长的数字串 你抓狂了 究竟哪个才是真正的咒语呢 你突然想到 这两个都不是咒语 不妨称之为伪咒语 而真正的咒语却与他们有着密切的联系 于是你打开拜月亲手给你写的纸条 The Real Incantation is Their Common Increasing Subsequence of Maximal Possible Length 该死的拜月 居然还会 E 文 你咒骂着 但为了一家老小的生命 又不得不卖命地算着咒语的 长度 输入格式 输入文件中的第一行为一个数 N 代表有 N 组测试数据 对于每组测试数据 描述了两条数字串 首先一个数字为一条伪咒语的长度 M 接下来 M 个数描述了 伪咒语的内容 输出格式 输出文件中共 N 行 每行一个数字 描叙了对应咒语的长度 输入输出样例 输入 1 5 1 4 2 5 12 4 12 1 2 4 输出 2 数据范围 对于 100 的数据 有 1 N 5 1 M 500 Ai Bi 在长整型范围内 动态规划练习 13 天堂的馈赠 问题背景 小杉找到了做棉花糖的最优方案 想去摘云朵 可是摔死了 他来到了天堂 天堂当然是很大的 也是很缭乱的 小杉看到一块路标 写着 天堂的馈赠 问题描述 考虑到小杉刚死没多久 为了安抚他受创的心灵和思恋的感情 天堂派出一个天使给小杉送礼 但 IQ 不够高的小杉可不能够拿到好礼物 馈赠在天堂门口进行 天使站在云端 往下扔礼物 天堂之门的宽度为 W 格 按 1 W 编号 高度为 0 格 云端的高度为 H 格 小杉只能站在格子里 开始时 第 0 秒 小杉站在天堂之门的第 P 格 馈赠开始后 天使会在某些时刻从云端的某格扔礼物下来 礼物下落的速度 格 秒 是不一样的 小杉左右移动去接礼物 每秒可以移动 1 格或不移动 礼物之间的价值当然是不一样的 小杉事先知道了每个礼物的价值 当礼物在某一秒末恰好到达小杉所在的格子中 小杉就接到了这个礼物 小杉想知道 他最多可以拿到价值为多少的礼物 而且 由于礼物下落的速度有些可以很 小杉还想知道是不是有些礼物他怎么样也拿不到 输入格式 输入文件中的第一行有四个数 W P H N 1 P W 500 1 H 500 0 N 3000 接下来 N 行 每行四个数 t r v s 0 t 1500 1 r W 1 v H s 1e5 表示天使在 t 时刻 云端的第 r 格 以 v 格 秒的速度扔下价值 s 的礼物 输入均为正整数 输出格式 输出文件中有两行 第一行仅有一个整数 表示小杉最多能拿到价值多少的礼物 第二行也仅有一个整数 表示小杉不可能拿到的礼物总价值多少 输入输出样例 输入 1 1 1 1 1 1 1 1 输出 1 0 注释 注意 当礼物在某一秒末恰好到达小杉所在的格子中 小杉才能接到这个礼物 数据范围 10 的数据 W 100 H 100 N 200 动态规划练习 14 上帝的爱好 问题背景 拿了一些礼物 小杉想走进天堂 可却被拦了下来 因为上帝很喜欢词这个文体 他要求小杉必须写几首词来应对 写的词越多 能带进天堂的刚才拿的礼物就越多 问题描述 我们知道 词都是按照词牌来填的 上帝为了考验小杉 只给了他四种词牌 但只要压韵就算符合 词牌 小杉已经想好了 N 个意境优美的句子 每个句子都有一个韵脚 符合要求的词的句式应当有如下四种 XXYY XYXY XYYX XXXX 其中 X 或 Y 表示韵脚 现在小杉想知道 从他想的 N 个句子之中 最多能按顺序挑选出几首符合条件的词 并且词的句子间不能交错 比如你选了 1 4 6 8 做为一首诗 那么 7 你就不能再选了 输入格式 输入文件中的第一行有一个数 N N 4000 第二行有 N 个不超过 10000 的正整数 第 i 个整数表示第 i 个句子的韵脚 整数相同表示韵脚相同 输出格式 输出文件中仅一行一个数字 表示小杉最多能挑出几首词来 输入输出样例 输入 12 1 2 4 2 3 1 2 2 1 1 2 2 输出 2 注释 样例最多可以挑出两首词 一种方案如下 1 2 4 6 9 10 11 12 数据范围 30 的数据 N 100 动态规划练习 15 苹果旅游 问题背景 xiaoT 发现山谷相当的大 准确地说应该是相当的长 xiaoT 想到山谷的那头去看看 但是靠 xiaoT 走路的速度 到那边要 n 年 还好 xiaoT 可以买一些苹果 苹果买苹果 自相残杀 or 大义灭亲 它把这些苹果当成动力 根据火箭发射的原理 晕 这个苹果知道得真多 如果 xiaoT 把苹果向后扔 xiaoT 就会向前进 Q xiaoT 能把苹果扔多远 A xiaoT 拥有超强的臂力 Q xiaoT 怎么会有手呢 A 问题描述 苹果有两种 一种青苹果 一种红苹果 已知到山谷的长度为 k 用一些 同一种类 苹果可以通过的路程为 1 苹果的价格是不一样的 红苹果的价格是红苹果个数的四次方 青苹果的价格就是青苹果个数 输入格式 输入文件中的第一行有一个正整数 n 表示 xiaoT 走路到那边需要的时间 第二行有一个正整数 k 表示山谷的长度 接下来 k 行 每行两个正整数 分别表示通过该段 如果使用红苹果 则需要的数量为 a 如果使用青苹果 则需要的数量为 b 输出格式 输出文件中只有一个数 即买苹果的最少的花费 输入输出样例 输入 2296 3 3 1000 2 5000 4 8000 输出 2296 样例解释 第1段用青苹果 第2 3段用红苹果 花费是1000 2 4 4 数据范围 对于30 的数据 k 10 对于50 的数据 k 25 对于100 的数据 k 50 对于100 的数据 每段路消耗的红苹果的数量 10 动态规划练习 16 对于100 的数据 每段路消耗的青苹果的数量 107 文科生的悲哀 问题背景 化学不及格的 Matrix67 无奈选择了文科 他必须硬着头皮艰难地进行着文科的学习 问题描述 这学期的政治 历史和地理课本各有 n 章 每一科的教学必须按章节从前往后依次进行 若干章政 治 若干章历史和若干章的地理内容可以合成一个教学阶段 年级计划将整个学期的内容分成若干个阶 段进行教学 为了保证各科教学进度相同 年级规定每一个阶段包含的各科的章节数必须相同 一个阶 段包含的章节越多 这个阶段所需要的课时也就越多 经过研究 假如某个阶段包含政史地各 k 章 则 政治学习需要花费 3 k 天的课时 历史学习需要花费 5 k 天的课时 地理学习需要花费 2 k 天的课时 最后还需要 4 天的综合训练 一个阶段所花费的总时间是以上四项时间的和 为了便于安排时间 学校希望每个阶段恰好需要若干周来完成 因此 划分出的每一个阶段所需要 的天数都必须是 7 的整数倍 高三是没有星期六和星期天的 那么 这学期的课程最多可以划分成多少个阶段呢 你会想到 要想划分的阶段数最多 一个阶段 完成一章的任务就行了 因为 3 1 5 1 2 1 4 14 是 7 的整数倍 但问题没有这么简单 每个课本都可 能有一些独立性较强的连续章节 它们具有很强的连续性 必须在一个阶段中完成 如果你已知所有不 能划分在两个或两个以上的阶段中的连续章节 你还能计算出最多能安排多少个阶段吗 输入格式 输入文件中的第一行有两个用空格隔开的正整数 n 和 m 分别表示各科课本的章节数和不可分割的连 续章节的个数 第二行到第 m 1 行 每行告诉了一个信息 该信息说明了哪一个课本的第几章到第几章必须一次性 完成 同一科目给定的章节有可能重复或有重叠 每一行信息分为两个部分 第一部分是 Politics History Geography 三个字符串中的 一个 第二部分是用 连接的两个数字 x y 1 x y n 表示该行第一部分所示的课本从第 x 章到 第 y 章具有连续性 第二部分紧接在第一部分后面 没有任何符号分隔 输出格式 一个正整数 表示按照学校和年级的种种要求 见下 最多可以安排的阶段个数 如果没有符合条件的安排方案 请输出 1 注意 以下三个要求需要同时考虑 1 每一个阶段包含的各科章数相同 2 按时间函数计算出的各阶段所需天数必须是 7 的倍数 3 给出的任一个连续章节都不能被分割开来 输入输出样例 输入 8 3 Politics 1 2 History 5 6 Politics 1 4 动态规划练习 17 输出 3 样例说明 最多可以安排三个阶段 具体方案如下 第一阶段完成各科第 1 6 章的课程 第二阶段完成各科第 7 章的课程 第三阶段完成各科第 8 章的课程 Sample Input 2 4 2 Geography 1 3 History 2 4 Sample Output 2 1 数据范围 对于 30 的数据 n m 10 对于 50 的数据 n m 1000 对于 100 的数据 n m 100000 动态规划练习 18 硬 件 问题描述 OIBH 运来一批装备 鼠标和键盘 DaoThree 要把这些装备分配给 moderator 们 每人一个鼠标 一个键盘 可是问题来了 这些装备的型号不相同 把一个 m 型的键盘和一个 n 型的鼠标分配给一个 moderator 得到的不满意 值为 m n 2 每个 moderator 当然希望自己得到的装备是同一型号的 你的任务就是帮帮 DaoThree 把 a 个键盘和 b 个鼠标分配给 n 个 moderator 使他们的不满意值之和 最小 输入格式 输入文件中的第一行 三个正整数 n a b 1 n a b 80 第二行 a 个数表示每个键盘的型号 第三行 b 个数表示每个鼠标的型号 0 型号值 10000 输出格式 输出文件中仅一个数 即最小不满意值 输入输出样例 输入 1 2 3 3 9 10 20 0 10 11 输出 1 2 输入 2 3 4 4 3 9 7 4 4 2 5 5 输出 2 5 数据范围 对于 30 的数据 n 10 a b 30 对于 100 的数据 n 75 a b 80 动态规划练习 19 糖果盒 问题描述 一个被分为 n m 个格子的糖果盒 第 i 行第 j 列位置的格子里面有 a i j 颗糖 本来 tenshi 打算 送这盒糖果给某 PPMM 的 但是就在要送出糖果盒的前一天晚上 一只极其可恶的老鼠夜袭糖果盒 有部 分格子被洗劫并且穿了洞 tenshi 必须尽快从这个糖果盒里面切割出一个矩形糖果盒 新的糖果盒不能 有洞 并且 tenshi 希望保留在新糖果盒内的糖的总数尽量多 任务 请帮 tenshi 设计一个程序计算一下新糖果盒最多能够保留多少糖果 输入格式 输入文件中的第一行有两个整数 n m 1 n m 300 第 i 1 行的第 j 个数表示 a i j 0 a i j 255 如果这个数为 0 则表示这个位置的格子被 洗劫过 输出格式 输出文件中为最大糖果数 输入输出样例 输入 3 4 1 2 3 4 5 0 6 3 10 3 4 0 输出 17 注意 10 3 4 这个矩形的糖果数最大 动态规划练习 20 能量项链 问题描述 在 Mars 星球上 每个 Mars 人都随身佩带着一串能量项链 在项链上有 N 颗能量珠 能量珠是一颗 有头标记与尾标记的珠子 这些标记对应着某个正整数 并且 对于相邻的两颗珠子 前一颗珠子的尾 标记一定等于后一颗珠子的头标记 因为只有这样 通过吸盘 吸盘是 Mars 人吸收能量的一种器官 的 作用 这两颗珠子才能聚合成一颗珠子 同时释放出可以被吸盘吸收的能量 如果前一颗能量珠的头标 记为 m 尾标记为 r 后一颗能量珠的头标记为 r 尾标记为 n 则聚合后释放的能量为 m r n Mars 单位 新产生的珠子的头标记为 m 尾标记为 n 需要时 Mars 人就用吸盘夹住相邻的两颗珠子 通过聚合得到能量 直到项链上只剩下一颗珠子为 止 显然 不同的聚合顺序得到的总能量是不同的 请你设计一个聚合顺序 使一串项链释放出的总能 量最大 例如 设 N 4 4 颗珠子的头标记与尾标记依次为 2 3 3 5 5 10 10 2 我们用记号 表示两颗珠子的聚合操作 j k 表示第 j k 两颗珠子聚合后所释放的能量 则第 4 1 两颗珠子聚合 后释放的能量为 4 1 10 2 3 60 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 4 1 2 3 10 2 3 10 3 5 10 5 10 710 输入格式 输入文件中的第一行是一个正整数 N 4 N 100 表示项链上珠子的个数 第二行是 N 个用空格隔开的正整数 所有的数均不超过 1000 第 i 个数为第 i 颗珠子的头标记 1 i N 当 i N 时 第 i 颗珠子的尾标记应该等于第 i 1 颗珠子的头标记 第 N 颗珠子的尾标记应 该等于第 1 颗珠子的头标记 至于珠子的顺序 你可以这样确定 将项链放到桌面上 不要出现交叉 随意指定第一颗珠子 然 后按顺时针方向确定其他珠子的顺序 输出格式 输出文件中只有一行 是一个正整数E E 2 1 109 为一个最优聚合顺序所释放的总能量 输入输出样例 输入 4 2 3 5 10 输出 710 动态规划练习 21 金明的预算方案 问题描述 金明今天很开心 家里购置的新房就要领钥匙了 新房里有一间金明自己专用的很宽敞的房间 更 让他高兴的是 妈妈昨天对他说 你的房间需要购买哪些物品 怎么布置 你说了算 只要不超过 N 元钱就行 今天一早 金明就开始做预算了 他把想买的物品分为两类 主件与附件 附件是从属于某 个主件的 下表就是一些主件与附件的例子 主件附件 电脑打印机 扫描仪 书柜图书 书桌台灯 文具 工作椅无 如果要买归类为附件的物品 必须先买该附件所属的主件 每个主件可以有 0 个 1 个或 2 个附件 附件不再有从属于自己的附件 金明想买的东西很多 肯定会超过妈妈限定的 N 元 于是 他把每件物 品规定了一个重要度 分为 5 等 用整数 1 5 表示 第 5 等最重要 他还从因特网上查到了每件物品的 价格 都是 10 元的整数倍 他希望在不超过 N 元 可以等于 N 元 的前提下 使每件物品的价格与重 要度的乘积的总和最大 设第 j 件物品的价格为 v j 重要度为 w j 共选中了 k 件物品 编号依次为 j1 j2 jk 则 所求的总和为 v j1 w j1 v j2 w j2 v jk w jk 其中 为乘号 请你帮助金明设计一个满足要求的购物单 输入格式 输入文件中的第一行 为两个正整数 用一个空格隔开 N m 其中 N N 32000 表示总钱数 m m 60 为希望购买物品的个数 从第二行到第 m 1 行 第 j 行给出了编号为 j 1 的物品的基本数据 每行有 3 个非负整数 v p q 其中 v 表示该物品的价格 v0 表示该物品为附件 q 是所属主件的编号 输出格式 输出文件中只有一个正整数 为不超过总钱数的物品的价格与重要度乘积的总和的最大值 200000 输入输出样例 输入 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 输出 2200 动态规划练习 22 潜水员 问题描述 潜水员为了潜水要使用特殊的装备 他有一个带两种气体的气缸 一个为氧气 一个为氮气 让潜 水员下潜的深度需要各种的数量的氧和氮 潜水员有一定数量的气缸 每个气缸都有重量和气体容量 潜水员为了完成他的工作需要特定数量的氧和氮 他完成工作所需气缸的总重的最低限度的是多少 例如 潜水员有 5 个气缸 每行三个数字为 氧 氮的 升 量和气缸的重量 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 如果潜水员需要 5 升的氧和 60 升的氮则总重最小为 249 1 2 或者 4 5 号气缸 你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值 输入格式 输入文件中的第一行有两个整数 t a 1 t 21 1 a 79 它们表示氧 氮各自需要的量 第二行为整数 n 1 n 1000 表示气缸的个数 此后的 n 行 每行包括 ti ai wi 1 ti 21 1 ai 79 1 wi 800 三个整数 它们分别是 第 i 个气缸里的氧和氮的容量及汽缸重量 输出格式 输出文件中仅一行包含一个整数 为潜水员完成工作所需的气缸的重量总和的最低值 输入输出样例 输入 5 60 5 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 输出 249 动态规划练习 23 观光游览 问题描述 一条街道被分成 m 格 1 m 100 还有 n 个景点 1 n 100 分布在街道上 每个景点可以占 据连续的若干格 并且有一个美学值 v 0 v 100 现要组织 k 个人考察这个街道 1 k m 每个人 考察的区域是连续的若干格 不可为 0 格 且任意两个人考察的区域不得相交 也不得有一个格子无人 考察 对于任意一个人 如果它考察的区域中有一个风景点 风景点必须完整的位于这个区域 则它就 得到了这个风景点的分值 美学值 你的任务是将街道的 m 个格子分给 k 个人去考察 使得总的分值最大 输入格式 输入文件中的第一行一个整数 m 表示街道的长度 第二行一个整数 n 表示风景点个数 此后 n 行 每行描述一个风景点 三个整数 x y 和 v 表示该风景点是从第 x 个格子到第 y 个格子 美学值为 v 最后一行一个整数 k 表示考察的人数 输出格式 输出文件仅一个整数 表示最大可以得到的分值 输入输出样例 输入 3 2 1 2 2 2 3 3 2 输出 3 动态规划练习 24 任务安排 问题描述 N 个任务排成一个序列在一台机器上等待完成 顺序不得改变 这 N 个任务被分成若干批 每批包 含相邻的若干任务 从时刻 0 开始 这些任务被分批加工 第 i 个任务单独完成所需的时间是 Ti 在每 批任务开始前 机器需要启动时间 S 而完成这批任务所需的时间是各个任务需要时间的总和 同一批任 务将在同一时刻完成 每个任务的费用是它的完成时刻乘以一个费用系数 Fi 请确定一个分组方案 使 得总费用最小 例如 S 1 T 1 3 4 2 1 F 3 2 3 3 4 如果分组方案是 1 2 3 4 5 则 完成时间分别为 5 5 10 14 14 费用 C 15 10 30 42 56 总费用就是 153 输入格式 输入文件中的第一行是 n 1 n 5000 第二行是 s 0 s 50 下面 n 行每行有一对数 分别为 Ti和 Fi 均为不大于 100 的正整数 表示 第 i 个任务单独完成所需的时间是 Ti及其费用系数 Fi 输出格式 输出文件中仅一个数 最小的总费用 输入输出样例 输入 5 1 1 3 3 2 4 3 2 3 1 4 输出 153 动态规划练习 25 筷子 问题描述 A 先生有很多双筷子 确切的说应该是很多根 因为筷子的长度不一 很难判断出哪两根是一双的 这天 A 先生家里来了 K 个客人 A 先生留下他们吃晚饭 加上 A 先生 A 夫人和他们的孩子小 A 共 K 3 个人 每人需要用一双筷子 A 先生只好清理了一下筷子 共 N 根 长度为 T1 T2 T3 TN 现在他 想用这些筷子组合成 K 3 双 使每双的筷子长度差的平方和最小 怎么不是和最小 这要去问 A 先生了 呵呵 输入格式 输入文件中共两行 第一行为两个用空格隔开的整数 表示 N K 1 N 100 0 K 50 第二行共有 N 个用空格隔开的整数 为 Ti每个整数为 1 50 之间的数 输出格式 输出文件中仅一行 如果凑不齐 K 3 双 输出 1 否则输出长度差平方和的最小值 输入输出样例 输入 10 1 1 1 2 3 3 3 4 6 10 20 输入 5 说明 第一双 1 1 第二双 2 3 动态规划练习 26 递增序列 问题描述 给定一个数字串 请你插入若干个逗号 使得该数字串成为一个严格递增的数列且最后一个数要尽 可能小 在这个问题中 前导的零是允许出现在数的前面的 输入格式 输入文件中仅有一行 为一个长度不超过 80 的数字串 输出格式 输出一个严格递增且最后一数最小的数列 相邻两个数之间用一个逗号隔开 如果有多个数列满足 要求 则输出第一个数最大的那个数列 若这样的解还不止一个 则输出第二个数最大的那个数列 以 此类推 输入输出样例 输入 100000101 输出 100 000101 动态规划练习 27 POWER 问题描述 多瑞卡得到了一份有趣而高薪的工作 每天早晨他必须关掉他所在村庄的街灯 所有的街灯都被设 置在一条直路的同一侧 多瑞卡每晚到早晨 5 点钟都在晚会上 然后他开始关灯 开始时 他站在某一盏路灯的旁边 每盏灯都有一个给定功率的电灯泡 因为多端卡有着自觉的节能意识 他希望在耗能总数最少的情 况下将所有的灯关掉 多端卡因为太累了 所以只能以 1m s 的速度行走 关灯不需要花费额外的时间 因为当他通过时就 能将灯关掉 编写程序 计算在给定路灯设置 灯泡功率以及多端卡的起始位置的情况下关掉所有的灯需耗费的 最小能量 输入格式 输入文件中的第一行包含一个整数 N 2 N 1000 表示该村庄路灯的数量 第二行包含一个整数 V 1 V N 表示多瑞卡开始关灯的路灯号码 接下来的 N 行中 每行包含两个用空格隔开的整数 D 和 W 0 D 1000 0 W 1000 用来描述每 盏灯的参数 D 表示该路灯与村庄开始处的距离 用米为单位来表示 W 表示灯泡的功率 即在每秒种 该灯泡所消耗的能量数 路灯是按顺序给定的 输出格式 输出文件中的第一行即唯一的一行应包含一个整数 即消耗能量之和的最小值 注意 结果小超过 1000000000 输入输出样例 输入 4 3 2 2 5 8 6 1 8 7 输出 56 动态规划练习 28 清扫 问题描述 现在要打扫国王的牧圈 已经 30 年没打扫了 所以这次的计划是用河水来冲 牧圈排成整齐的格子 每相邻的两个之间都有门 要想让水进去 就必须打开这些门 这不是件容 易的事情 因为有些圈里土堆得很高 因此打开门就很费劲 为了使花的力气最小 总是把门推向土低 的一边 你的任务是计算最少得费多少劲 我们用土的厚度来描述这个值 输入格式 输入文件中的第一行是宽度 w 和高度 h 3 w h 40 以下 h 行数据 描述了土的高度 也就是我们所浪费体力的度量 数据的范围在 1 到 100 之间 输出格式 你得到的结果 所有的格子都必须进水 水是从左上角的格子进去的 输入输出样例 输入 4 3 3 5 2 1 7 3 4 8 1 6 5 7 输出 26 动态规划练习 29 破译密码 问题描述 Feli 得到总部发来的消息 我军特种部队已经截获敌人的一个密码本 但是这个密码本本身是由密 码写成的 为了给敌人造成沉重的打击 Feli 必须尽快破译密码 经过一天一夜的探索 Feli 发现日军密码本实际上记载着一个数列 而最终密码由这个数列经过某 种运算得到 运算是这样的 1 把数列从小到大排序 2 分拆分拆 在排好序的数列中 任选一个数 这个数将把原数列分成左右两个数列 选出的数不 在新数列中 并且新数列有可能为空 3 对每个新数列进行第 2 步操作 直到最后得到的数列长度都为 1 即全部变成单个数 4 将第 3 步得到的每个数 得到它所需的分拆次数 1 累加得到一个和 5 重复 2 3 4 操作 直到遍历所有的分拆可能 这时 所得的和当中最小的一个就是日军的最 终密码 6 现在 Feli 请求你帮助 尽快破译这段密码 输入格式 输入数据第一行为 N N 1000 表示密码本记录的数列的长度 下一行共有 N 个数 即日军密码本记载的数列 输出格式 输出数据为一个整数 即日军最终密码 输入输出样例 输入 3 1 3 2 输出 10 说明 1 数列排序得 1 2 3 2 选出一个数 2 3 分拆得 2 1 3 此时新的数列 1 3 长度都已经是 1 因此无须再分拆 4 求和 2 1 1 2 3 2 10 2 在原数列 故乘 1 1 和 3 都经过一次分拆 故乘 2 2 选出一个数 1 3 分拆得 1 2 3 动态规划练习 30 2 3 中选一个数 2 分拆得 1 2 3 4 求和 1 1 2 2 3 3 14 所有和当中最小的是所有和当中最小的是 1010 故输出 故输出 1010 动态规划练习 31 奶牛家谱 问题描述 农民约翰准备购买一群新奶牛 在这个新的奶牛群中 每一个母亲奶牛都生两小奶牛 这些奶牛间 的关系可以用二叉树来表示 这些二叉树总共有 N 个节点 3 N 200 这些二叉树有如下性质 每一个节点的度是 0 或 2 度是这个节点的孩子的数目 树的高度等于 K 1 K 100 高度是从根到任何叶子的最长的路径上的节点的数目 叶子是指没有孩 子的节点 有多少不同的家谱结构 如果一个家谱的树结构不同于另一个的 那么这两个家谱就是不同的 输 出可能的家谱树的个数除以 9901 的余数 输入格式 输入文件中的第一行 两个空格分开的整数 N 和 K 输出格式 输出文件中的第一行 一个整数 表示可能的家谱树的个数除以 9901 的余数 输入输出样例 输入 5 3 输出 2 OUTPUT DETAILS 有 5 个节点 高为 3 的两个不同的家谱 动态规划练习 32 集合 问题描述 对于从 1 到 N 的连续整集合合 能划分成两个子集合 且保证每个集合的数字和是相等的 举个例子 如果 N 3 对于 1 2 3 能划分成两个子集合 他们每个的所有数字和是相等的 3 and 1 2 这是唯一一种分发 交换集合位置被认为是同一种划分方案 因此不会增加划分方案总数 如果 N 7 有四种方法能划分集合 1 2 3 4 5 6 7 每一种分发的子集合各数字和是相等的 1 6 7 and 2 3 4 5 注 1 6 7 2 3 4 5 2 5 7 and 1 3 4 6 3 4 7 and 1 2 5 6 1 2 4 7 and 3 5 6 给出 N 你的程序应该输出划分方案总数 如果不存在这样的划分方案 则输出 0 程序不能预存结 果直接输出 输入格式 输入文件只有一行 且只有一个整数 N 输出格式 输出划分方案总数 如果不存在则输出 0 输入输出样例 输入 7 输出 4 动态规划练习 33 书本整理 问题描述 Frank 是一个非常喜爱整洁的人 他有一大堆书和一个书架 想要把书放在书架上 书架可以放下所 有的书 所以 Frank 首先将书按高度顺序排列在书架上 但是 Frank 发现 由于很多书的宽度不同 所 以书看起来还是非常不整齐 于是他决定从中拿掉 k 本书 使得书架可以看起来整齐一点 书架的不整齐度是这样定义的 每两本书宽度的差的绝对值的和 例如有 4 本书 1 2 5 3 2 4 3 1 那么 Frank 将其排列整齐后是 1 2 2 4 3 1 5 3 不整齐度就是 2 3 2 7 已知每本书的高度都不一样 请你求出去掉 k 本书后的最小的不整齐度 输入格式 输入文件中的第一行两个数字 n 和 k 1 n 100 1 k n 代表书有几本 从中去掉几本 下面的 n 行 每行两个数字表示一本书的高度和宽度 均小于 200 输出格式 一行一个整数 表示书架的最小不整齐度 输入输出样例 输入 4 1 1 2 2 4 3 1 5 3 输出 3 动态规划练习 34 城堡 问题描述 某国聪明美丽的公主要找一位如意郎君 她希望未来的夫君是一个聪明善良 节俭但又不吝啬的人 为了找到理想的人选 她的爸爸 国王 给她修建了一座城堡 这个城堡有很多房间 房间之间有走廊 连接 但每进入一个房间必须要花费一定数量的钱币 公主就在某个房间中等待 开始 国王给每个候 选人一样多的钱币 候选人从同一个地点出发 直到找到美丽的公主为止 如果这时哪个人找到了公主 并且钱币刚好用完 那么他将会赢得公主的芳心 很多天过去了 但没有一个人能成功 你想试试吗 假设肯定有解 输入格式 输入文件中的第一行有几个用单个空格分开的整数 n m e p b 1 n 100 1 m 4950 1 e p n 1 b 1000 其中 n 表示房间数 m 表示走廊 数 房间从 1 到 n 编号 e 是入口的房间号 p 公主所在的房间号 b 是每个人的初始钱币数 第二行有 n 个用单个空格分开的正整数 c1 c2 cn 1 ci 1000 其中 ci是进入第 i 间房间的 花费 下面 m 行 每行有两个正整数 x y xy 1 x y n 表示房间 x 和 y 之间的连接走廊 输出格式 输出文件中应该写入一连串用单个空格分开的整数 表示从入口到公主所在地路线所经过的房