荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: selahx (宿醉未散,早梦半醒), 信区: ACMICPC
标  题: 动态规划基础题库
发信站: 荔园晨风BBS站 (2005年04月23日12:44:09 星期六), 站内信件

0. 最大子串和
〖题目描述〗
在一个一维数组里找出连续的几个数,使数的总和最大。

1. 最短路(Shortest path)
〖题目描述〗
从A地到E地可以经过不同的路径,不同的路有不同的发费,问如何走可以得到耗费最少的
路径?

2. 最小中间和数
〖题目描述〗
给定一个正整数序列a1,a2,a3,……,an不改变序列中每个在序列中的位置,把它们相加,
并括号记每次加法所得的和,称为中间和。问如何加括号可以使所有的中间和相加为最少


3. 最长公共子序列问题:
〖题目描述〗
给定两个序列x=<x1,x2,x3,……,xn>和y=<y1,y2,……,ym>,要求找出x和y 的一个最长公共
子序列。

4、防卫导弹:
〖题目描述〗
一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行,也可以用很快的速度向下飞
行,可以毫无损伤地截击进攻导弹,但不可以向后或向上飞行。但有一个缺点,尽管它发
射时可以达到任意高度,但它只能截击比它上次截击导弹时所处高度低或者高度相同的导
弹。现对这种新型 防卫导弹进行测试,在每一次测试中,发射一系列的测试导弹(这些导
弹发射的间隔时间固定,飞行速度相同),该防卫导弹所能获得的信息包括各进攻导弹的
高度,以及它们发射次序。现要求编一程序,求在每次测试中,该防卫导弹最多能截击的
进攻导弹数量,一个导弹能被截击应满足下列两个条件之一:
1、它是该次测试中第一个被防卫导弹截击的导弹;
2、它是在上一次被截击导弹的发射后发射,且高度不大于上一次被截击导弹的高度的导弹

输入格式:从当前目录下的文本文件"CATCHER.DAT"读入数据 。该文 件的第一行是一个整
数N(0〈=N〈=4000),表示本次测试中,发射的进攻导弹数,以下N行每行各有一个整数
hi(0〈=hi〈=32767),表示第i个进攻导弹的高度。文件中各行的行首、行末无多余空格
,输入文件中给出的导弹是按发射顺序排列的。
输出格式:答案输出到当前目录下的文本文件"CATCHER.OUT"中,该文件第一行是一个整数
max,表示最多能截击的进攻导弹数,以下的max行每行各有一个整数,表示各个被截击的
进攻导弹的编号(按被截击的先后顺序排列)。输出的答案可能不唯一,只要输出其中任
一解即可。
输入输出举例:


输入文件:CATCHER.DAT
3
25
36
23
输出文件:CATCHER.OUT
2
1
3


5、轮船(Ships)
〖题目描述〗
有一个国家被一条何划分为南北两部分,在南岸和北岸总共有N个城镇,每一城镇在对岸都
有唯一的友好城镇。任何两个城镇都没有相同的友好城镇。每一对友好城镇都希望有一条
航线来往。于是他们向政府提出了申请。由于河终年有雾。政府决定不允许有任两条航线
交叉(如果两条航线交叉,将有很大机会撞船)。
你的任务是缟写一个程序来帮政府官员决定他们应拨款兴建哪些航线以使到没有出现交叉
的航线最多。
输入数据
输入文件(ship.in)包括了若干组数据,每组数据格式如下:
第一行两个由空格分隔的整数x,y,10〈=x〈=6000,10〈=y〈=100。x 表示河的长度而y
表示宽。第二行是一个整数N(1<=N<=5000),表示分布在河两岸的城镇对数。接下来的N行
每行有两个由空格分隔的正数C,D(C、D〈=x〉,描述每一对友好城镇沿着河岸与西边境
线的距离,C表示北岸城镇的距离而D表示南岸城镇的距离。在河的同一边,任何两个城镇
的位置都是不同的。整个输入文件以由空格分隔的两个0结束。
输出数据
输出文件(ship.ou)要在连续的若干行里给出每一组数据在安全条件下能够开通的最大航线
数目。
示例

Ship.in
30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
0 0

Ship.out
4

6.过桥问题
〖题目描述〗
    GDOI工作组遇到了一个运输货物的问题。现在有N辆车要按顺序通过一个单向的小桥,
由于小桥太窄,不能有两辆车并排通过,所以在桥上不能超车。另外,由于小桥建造的时
间已经很久,所以小桥只能承受有限的重量,记为Max(吨)。所以,车辆在过桥的时候必
须要有管理员控制,将这N辆车按初始顺序分组,每次让一个组过桥,并且只有在一个组中
所有的车辆全部过桥以后才让下一组车辆上桥。现在,每辆车的重量和最在速度是已知的
,而每组车的过桥时间由该组中速度最慢的那辆车决定。
现在请你编一个程序,将这N辆车分组,使得全部车辆通过小桥的时间最短。

输入格式:
数据存放在当前目录下的文本文件“bridge.in”中。
文件的第一行有三个数,分别为Max(吨),Len(桥的长度,单位:Km),N(三个数之间
用一个或多个空格分开)。
接下来有N行,每行两个数,第i行的两个数分别表示第i辆车的重量(吨)和最大速度(m
/s)。
注意:所有的输入都为整数,并且任何一辆车的重量都不会超过Max。

输出格式:
答案输出到当前目录下的文本文件“bridge.out”中。
文件只有一行,输出全部车辆通过小桥的最短时间(s),精确到小数点后一位。

输入输出样例:

bridge.in bridge.out
100 5 10
40 25
50 20
70 10
12 50
9 70
49 30
38 25
27 50
19 70 75.0

7. 复制书稿
〖题目描述〗
假设有M本书(编号为1,2,…M),想将每本复制一份,M本书的页数可能不同(分别是P
1,P2,…PM)。任务是将这M本书分给K个抄写员(K〈=M〉,每本书只能分配给一个抄写
员进行复制,而每个抄写员所分配到的书必须是连续顺序的。
意思是说,存在一个连续升序数列 0 = bo < b1 < b2 < … < bk-1 < bk = m,这样,第
I号抄写员得到的书稿是从bi-1+1到第bi本书。复制工作是同时开始进行的,并且每个抄写
员复制的速度都是一样的。所以,复制完所有书稿所需时间取决于分配得到最多工作的那
个抄写员的复制时间。试找一个最优分配方案,使分配给每一个抄写员的页数的最大值尽
可能小(如存在多个最优方案,只输出其中一种)。
(GDOI''99 Books).

〖输入格式〗
第一行两个数m,k:表示书本数目与人数;第二行m个由空格分隔的整数,m本书每本的页数.


〖输出格式〗
共k行。每行两个整数:第I行表示第I抄写员抄的书本编号起止。

〖输入输出样例〗

输入样例 输出样例
9 3
1 2 3 4 5 6 7 8 9  1 5
6 7
8 9

8. 石子归并
〖题目描述〗
在一个圆形操场的四周摆放着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
输出:
-4 5 9 -4
-8 -5 9
-13 -9
22

4 -5 -9 4
4 -14 -4
-4 -18
22


9. Perform巡回演出 (GDKOI'2000)
〖题目描述〗
   Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐
的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出
,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的
地Harp市(乐团可多次在同一城市演出).
   由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,
每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.
输入:
   输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开
始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Ha
rp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组
n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市
(1,3,4...n)的航班,如此下去.
   每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表
示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如
"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循
环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束.
输出:
   对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城
市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0.
样例输入:
3 6
2 130 150
3 75 0 80
7 120 110 0 100 110 120 0
4 60 70 60 50
3 0 135 140
2 70 80
2 3
2 0 70
1 80
0 0
样例输出:
460
0

10.Books
〖题目描述〗
 m个人抄n本书,每本书页数已知,每个人(第一个人除外)都必须从上一个人抄的最后一本书
的下一本抄起(书必须整本整本的抄),求一种分配方法,使抄书页数最多的人抄书页数尽可
能少. (GDOI''99 Books).

11. String
〖题目描述〗
 有一字符串有多种编码方式可供人选择,将这个字符串进行编码,使求得得编码长度最短
。 (GDKOI'2000 Compress)

12. Visit
〖题目描述〗
 Canada境内有自西向东的一系列城市:Halifax,Hamilton,Montelia,Vancouver...,各个
城市之间可能有航班相连,也可能没有,现要求从最西的城市出发,自西向东到达最东的
城市,再返回最西的城市,除最西城市外,其他每个城市只能访问一次,求最多能访问多
少个城市.

13. 旅行

------------------------------------------------------------------------------
--

提交文件名:tEWeLeyte

〖问题描述〗
GDOI队员们到Z镇游玩。Z镇是一个很特别的城镇,它有m+1条东西方向和n+1条南北方向的
道路,划分成m*n个区域。Z镇的名胜位于这些区域内。从上往下数第i行,从左往右数第j
列的区域记为D(i,j)。GDOI队员们预先对这m*n个区域打分V(i,j)(分数可正可负)。分数
越高表示他们越想到那个地方,越低表示他们越不想去。为了方便集合,队员们只能在某
一范围内活动。我们可以用(m1,nl)与(m2,n2)(m1<=m2,n1<=n2)表示这样的一个范围:它
是这些区域的集合:{D(i,j)|m1<=I<=m2,n1<=j<=n2}。GDOI队员们希望他们活动范围内的
区域的分值总和最大。
当然,有可能队员们一个地方也不去(例如,所有区域的分值都是负数。当然,如果某范串
内的分值总和为零的话,他们也会去玩)。也有可能他们游览整个Z镇。你的任务是编写一
个程序,求出他们的活动范围(m1,nl),(m2,n2〉。

〖输入格式〗
输入数据存放在当前目录下的文本文件"travel.dat"中。数据有m+1行。第一行有两个数m
,n(m,n定义如上)。其中,(1<=m<=250,1<=n<=250)。接下来的m行,每行n个整数,第
i行第j个数表示分值V(i,j)(-128<=V(i,j)<=l27)。每两个数之间有一个空格。

〖输出格式〗
答案输出到当前目录下?quot;travel.out"中,只有一行,分两种情况:
1.队员们在范围(m1,n1),(m2,n2)内活动,输出该范围内的分值。
2.队员们不想去任何地方,只需输出"NO"。
注意:不要有多余空行,行首行尾不要有多余空格。

〖输入输出举例〗

样例一
Travel.dat
4 5
1 -2 3 -4 5
6 7 8 9 10
-11 12 13 14 -15
16 17 18 19 20

travel.out
146

样例二
Travel.dat
2 3
-1 -2 -1
-4 -3 -6

travel.out
no

--


※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.64.1]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 210.39.3.80]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店