《动态规划47题》由会员分享，可在线阅读，更多相关《动态规划47题（57页珍藏版）》请在金锄头文库上搜索。
1、动态规划练习 - 1 -动态规划练习【题目一览】第一题 第二题 第三题 第四题 第五题题目名称 总分 邮票 家的范围 游戏 商店购物提交文件 inflate stamps range game shopping第六题 第七题 第八题 第九题 第十题题目名称 “破锣摇滚”乐 队 麦香牛块 最长前缀 货币系统 垃圾 陷阱提交文件 rockers nuggets prefix money well第十一题 第十二题 第十三题 第十四题 第十五题题目名称 神秘的咒语 天堂的馈赠 上帝的爱好 苹果旅游 文科生的悲哀提交文件 curse present like travel dole第十六题 第十七题
2、第十八题 第十九题 第二十题题目名称 硬件 糖果盒 能量项链 金明的预算方案 潜水员提交文件 hardware candy energy budget gas第二十一题 第二十二题 第二十三题 第二十四题 第二十五题题目名称 观光游览 任务安排 筷子 递增序列 power提交文件 view batch chop incsq power第二十六题 第二十七题 第二十八题 第二十九题 第三十题题目名称 清扫 破译密码 奶牛家谱 集合 书本整理提交文件 stables password nocows subset book第三十一题 第三十二题 第三十三题 第三十四题 第三十五题题目名称 城堡 简单
3、的网络 游戏 佳佳的魔杖 编码 将功补过提交文件 castle simple mwand codes inform第三十六题 第三十七题 第三十八题 第三十九题 第四十题题目名称 质数取石子 多人背包 不听话的机器人 路灯的改建计划 吃西瓜提交文件 pgame bags robot light matrix第四十一题 第四十二题 第四十三题 第四十四题 第四十五题题目名称 给 MM 的生日礼物 最勇敢的机器人 创意吃鱼法 爱心蜗牛 工作提交文件 gift bravest meal badnews Work第四十六题 第四十七题题目名称 最大矩形 座位安排动态规划练习 - 2 -提交文件 max
4、matrix seat总分【问题描述】学生在我们 USACO 的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分，这需要你的帮助。我们可以从几个种类中选取竞赛的题目，这里的一个“种类”是指一个竞赛题目的集合，解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉 USACO 的职员，应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。输入包括竞赛的时间 M（122）的个数。当然，放牧区域可能是重叠。【输入格式】输入文件中的第 1 行：N，牧区的边长。第 2 到 n+1 行：N 个没有空格分开的字符。0 表示“那
5、一个区段被毁坏了” ，1 表示“准备好被吃” 。【输出格式】输出那些存在的正方形的大小和个数，一种一行。【输入输出样例】输入：6101111001111111111001111101101111001输出：2 103 44 1动态规划练习 - 5 -游戏【问题描述】有如下一个双人游戏：N（20，表示该物品为附件，q 是所属主件的编号）【输出格式】输出文件中只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（y，13+1-2+2-63 条路径的价值，才 45，所以不可能完成任务。【数据规模】对于 30%的数据，保证有 N=1） ，描述池塘规模。接下来的 n 行，每行有 m 个数
6、字（非“0”即“1” ） 。每两个数字之间用空格隔开。【输出格式】输出文件中仅一个整数，即猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。【输入输出样例】输入：4 60 1 0 1 0 00 0 1 0 1 01 1 0 0 0 10 1 1 0 1 0输出：3【数据规模】对于 30%的数据，有 n，m_=1）【输出格式】输出文件中仅一个数，即最少工作时间。【输入输出样例】输入：315 0 2550 0 9045 15 70输出：50【数据规模】Ti=1，0=Ai，Bi=1200；对于 30%的数据，满足 n=5；对于 60%的数据，满足 n=500；对于 100%的数据，满足 n=100
7、0。输入数据保证 Bi-Ai 要大于等于 Ti，且小于 2Ti。动态规划练习 - 56 -最大矩形【问题描述】一个 NM 的矩阵，每个格子里面有个整数（绝对值不大与 10） ，每个子矩阵（至少包含一个元素）的价值就是它所包含的格子内的数的和。现在求两个不相交的子矩阵（不包含相同的格子） ，使得他们的价值的乘积最大。例如：N=3，M=4，矩阵如图所示：2 3 4 51 3 2 44 3 2 1最大子矩阵值乘积为 288。 （左边两列的和为 16，右边两列的和为 18，结果为 16*18=288） 。【输入格式】输入文件中的第一行有两个数字 n，m（n，m=100） 。以后的 n 行，每行有 m
8、个整数。【输出格式】输出文件中只有一个数，即两不相交子矩阵价值乘积的最大值。【输入输出样例】输入 1：1 7-9 -9 8 8 1 7 -4输出 1：128输入 2：3 42 3 4 51 3 2 44 3 2 1输出 2：288动态规划练习 - 57 -座位安排【问题背景】快要期中考试了！老师需要 hzy 帮他排考试的座位【问题描述】考场里的座位恰好有 n 行 m 列，并且恰好有 nm 位考生在这个考场里面考试，也就是说，所有的座位上都有考生。hzy 根据学校记载，有 k 位考生可能作弊，因此 hzy 不能让他们之中的任何两个人做在相邻的座位上！所谓相邻的座位，即在同一行相邻列或者在同一列的
9、相邻行的座位。hzy 准备这样安排座位，首先随机选择一种方案，如果这种方案是合法的，就用这种方案，否则重新选择。你的任务是计算，他得到一个合法方案时，需要的期望选择次数。【输入格式】输入文件中仅一行，包含三个整数 n，m 和 k。【输出格式】如果不存在合法的方案，则输出中应该包含“Impossible！” （不含引号） ，否则输出一个分数 p/q，表示期望选择次数（即平均次数） ，这里 p 和 q 应该是互质的。【输入输出样例】输入 1：1 4 3输出 1：Impossible!输入 2：2 3 2输出 2：15/8【数据范围】1=n=80，1=m=80，1=nm=80；0=k=20，并且 k=nm。
