动态规划部分常见题目.doc

动态规划部分常见题目 作者: 发表于2011-06-10 14:20:49 【大 中 小】 浏览:230次 评论:0条 ? 添加号 ? 有一个由数字1，2，... ，9组成的数字串（长度不超过200），问如何将M(M=20)个加号(+)插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。 ? 注意： ? 加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。 ? M保证小于数字串的长度。 ? 例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。 ? [输入格式] ? 数字串在输入文件的第一行行首（数字串中间无空格且不折行），Ｍ的值在输入文件的第二行行首。 ? [输出格式］ ? 在屏幕上输出所求得的最小和的精确值。 ? [输入输出举例］ ? EXAM4.SAM ? 82363983742 ? 3 ? ? 输 入 输 出 ? ? EXAM4.SAM 2170 ? 棋盘分割 ? 　将一个８×８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)? 允许的分割方案 不允许的分割方案 原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。 均方差??????????????? ，其中平均值???????? ?xi为第i块矩形棋盘的分。 请编程对给出的棋盘及n，求出 的最小值。 ? 第1行为一个整数n(1n15)。第2行至第9行每行为8个小于100的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。 ? 仅一个数，为 （四舍五入精确到小数点后三位）。 ? 31 1 1 1 1 1 1 31 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 01 1 1 1 1 1 0 3 ? 样例输出 ? 1.633 4.. ? 一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型 防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一： 1、 2、 输入格式： ? 从当前目录下的文本文件“CATCHER.DAT”读入数据。该文件的第一行是一个整数N（0〈=N〈=4000），表示本次测试中，发射的进攻导弹数，以下N行每行各有一个整数hi（0〈=hi〈=32767），表示第i个进攻导弹的高度。文件中各行的行首、行末无多余空格，输入文件中给出的导弹是按发射顺序排列的。 输出格式： ? 答案输出到当前目录下的文本文件“CATCHER.OUT”中，该文件第一行是一个整数max，表示最多能截击的进攻导弹数，以下的max行每行各有一个整数，表示各个被截击的进攻导弹的编号（按被截击的先后顺序排列）。输出的答案可能不唯一，只要输出其中任一解即可。 输入输出举例： ? 输入文件：CATCHER.DAT ? 输出文件：CATCHER.OUT 3 ? 2 25 ? 1 36 ? 3 23 ? ? ? ? 6.石子合并 ? 在一个圆形操场的四周摆放着N堆石子(N=? 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(=20). (!)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小; (2)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小; 输入数据: 第一行为石子堆数N; 第二行为每堆的石子数,每两个数之间用一个空格分隔. 输出数据: 从第一至第N行为得分最小的合并方案.第N+1行是空行.从第N+2行到第2N+1行是得分最大合并方案.每种合并方案用N行表示,其中第i行(1=i=N)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可).要求将待合并的两堆石子数以相应的负数表示. 输入输出范例