求两个字符串的最长公共子序列
0-1背包问题
骑士游历
设有一个n*m的棋盘(2<=n<=50,2<=m<=50),在棋盘上任一点有一个中国象棋马,马走的规则为:1.马走日字 2.马只能向右走.
任务1:当N,M 输入之后,找出一条从左下角到右上角的路径.
例如:输入 N=4,M=4
输出:路径的格式:(1,1)->(2,3)->(4,4)
若不存在路径,则输出"no"
任务2:当N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目.
例如:(N=10,M=10),(1,5)(起点),(3,5)(终点)
输出:2(即由(1,5)到(3,5)共有2条路径)
输入格式:n,m,x1,y1,x2,y2(分别表示n,m,起点坐标,终点坐标)
输出格式:路径数目(若不存在从起点到终点的路径,输出0)
数字三角形
（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
径，使该路径所经过的数字的总和最大。
●每一步可沿左斜线向下或右斜线向下走；
●1＜三角形行数≤100；
●三角形中的数字为整数0，1，…99；
输入数据：
由INPUT.TXT文件中首先读到的是三角形的行数。
在例子中INPUT.TXT表示如下：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出数据：
把最大总和（整数）写入OUTPUT.TXT文件。
上例为：
30
７
３ ８
８ １ ０
２ ７ ４ ４
４ ５ ２ ６ ５
（图３.１－１）
添加号
有一个由数字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(1<n<15)。
第2行至第9行每行为8个小于100的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。
输出
仅一个数，为
（四舍五入精确到小数点后三位）。样例输入
3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 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次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可).要求将待合并的两堆石子数以相应的负数表示.
输入输出范例:
输入:
4
4 5 9 4
输出:
－４ ５ ９ －４
－８ －５ ９
－１３ －９
２２
４ －５ －９ ４
４ －１４ －４
－４ －１８
２２
7..最小代价子母树
设有一排数，共ｎ个，例如：22 14 7 13 26 15 11.任意2个相邻的数可以进行归并,归并的代价为该两个数的和,经过不断的归并,最后归为一堆,而全部归并代价的和称为总代价,给出一种归并算法,使总代价为最小.
输入、输出数据格式与“石子合并”相同。
输入样例：
4
12 5 16 4
输出样例：
－１２ －５ １６ ４
１７ －１６ －４
－１７ －２０
３７
8.背包问题
设有ｎ种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为ＸＫ，今从ｎ种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于ＸＫ，而价值的和为最大。
输入数据：
第一行两个数：物品总数Ｎ，背包载重量ＸＫ；两个数用空格分隔；
第二行N个数,为Ｎ种物品重量；两个数用空格分隔；
第三行N个数,为N种物品价值; 两个数用空格分隔；
输出数据：
第一行总价值；
以下N行，每行两个数，分别为选取物品的编号及数量；
输入样例：
4 10
2 3 4 7
1 3 5 9
输出样例：
12
2 1
4 1
9.商店购物
某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）;一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU ;2个花瓶加1朵花是10 ICU不是12 ICU。
编一个程序，计算某个顾客所购商品应付的费用。 要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量， 即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述， 并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU因为:
1朵花加2个花瓶: 优惠价:10 ICU
2朵花 正常价: 4 ICU
输入数据
用两个文件表示输入数据。第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT）。 两个文件中都只用整数。
第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。 C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。
第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤9 9），表示共有S 种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤ P≤9999）代表此商品组合的优惠价。当然， 优惠价要低于该组合中商品正常价之总和。
输出数据
在输出文件OUTPUT．TXT中写 一个数字（占一行）， 该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。
输入/输出数据举例
┌────────┐ ┌────────────┐┌────────┐
│ INPUT │ │ OFFER．TXT ││ OUTPUＴ．TXT│
├────────┤ ├────────────┤├────────┤
│ 2 │ │ 2 ││ 14 │
│ ７ ３ ２ │ │ 1 7 3 5 ││ │
│ ８ ２ ５ │ │ 2 7 1 8 2 10 ││ │
└────────┘ └─
化工厂装箱员
118号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有3种不同的纯度，A：100%，B：1%，C：0.01%，为了出售方便，必须把不同纯度的成品分开装箱，装箱员grant第1次顺序从流水线上取10个成品（如果一共不足10个，则全部取出），以后每一次把手中某种纯度的成品放进相应的箱子，然后再从流水线上顺序取一些成品，使手中保持10个成品（如果把剩下的全部取出不足10个，则全部取出），如果所有的成品都装进了箱子，那么grant的任务就完成了。
由于装箱是件非常累的事情，grant希望他能够以最少的装箱次数来完成他的任务，现在他请你编个程序帮助他。
输入
第1行为n（1<=n<=100），为成品的数量
以后n行，每行为一个大写字母A，B或C，表示成品的纯度。
输出
仅一行，为grant需要的最少的装箱次数。
输入样例
11
A
B
C
A
B
C
A
B
C
A
B
输出样例
3
方格取数
问题描述
设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：
向右
A 1 2 3 4 5 6 7 8
0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 13
| 0
| 0
| 6
| 0
| 0
| 0
| 0
| 0
| 0
| 7
| 0
| 0
| 0
| 0
| 0
| 0
| 14
| 0
| 0
| 0
| 0
| 0
| 21
| 0
| 0
| 0
| 4
| 0
| 0
| 0
| 0
| 15
| 0
| 0
| 0
| 0
| 0
| 0
| 14
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
| 0
|
|
某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输 入
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
输 出
只需输出一个整数，表示2条路径上取得的最大的和。
样 例 ：
输 入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输 出
67
