文档介绍：该【动态规划习题 】是由【大笑大甜】上传分享，文档一共【26】页，该文档可以免费在线阅读，需要了解更多关于【动态规划习题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。..
动向规划专题分类视图
数轴动规题:1
较复杂的数轴动规4
线性动规7
地区动规:14
未知的动规:20
数轴动规题:
--装箱问题
【问题描绘】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物件(0<n≤30),每个物件有一个
体积(正整数)。要求从n个物件中,任取若干个装入箱内,使箱子的节余空间为最小。
【输入格式】。第一行:一个整数,表示箱子容量V;
第二行:一个整数,表示物件个数n;接下来n行,分别表示这n个物件的各自体积。
【输出格式】,该行只有一个数,表示最小的箱子节余空间。
【输入样例】
24
6
8
3
12
7
9
7
【输出样例】
0
年提升组第4题--砝码秤重
__数据增强版
【问题描绘】设有n种砝码,第k种砝码有
Ck个,每个重量均为
Wk,求:用这些砝码能秤出的不同重量
;.
..
的个数,但不包含一个砝码也不用的状况。
【输入格式】,表示不同的砝码的种类数.
第2行至第n+1行,+1行的两个数分别表示第k种砝码的个数和重量.
【输出格式】:Total=N。表示用这些砝码能秤出的不同重量数。
【输入样例】
2
22
23
【输出样例】
Total=8
【样例说明】
重量2,3,4,5,6,7,8,10都能秤得
【数据限制】
对于100%的数据,砝码的种类n知足:1≤n≤100;
对于30%的数据,砝码的总数目C知足:1≤C≤20;
对于100%的数据,砝码的总数目C知足:1≤C≤100;
对于所有的数据,砝码的总重量W知足:1≤W≤400000;
-
【问题描绘】有一堆石头质量分别为W1,W2,,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。
【输入】(1≤n≤50),表示有n堆石子。接下去的n行,为每堆石子质量。
【输出】,该行只有一个整数,表示最小的质量差.
【样例输入】
5
5
8
13
27
14
【样例输出】
3
【问题描绘】有四个人,每人身上的衣服分别有s1,s2,s3和s4处损坏,并且每处损坏程度不同,损坏程
度用需修睦它用的时间表示(A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。可是你能够同时修理2处损坏。但
是这2处损坏,只好是同一件衣服上的。就是说你只好同时修理一件衣服,修睦了,才能修理下一件。
【输入】本题包含5行数据:第1行,为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20)
第2行,为A1...As1共s1个数,表示第一件衣服上每个损坏修睦它所需的时间第3行,为B1...Bs2共s2个数,表示第二件衣服上每个损坏修睦它所需的时间
第4行,为C1...Cs3共s3个数,表示第三件衣服上每个损坏修睦它所需的时间第5行,为D1...Ds4共s4个数,表示第四件衣服上每个损坏修睦它所需的时间
(1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60)
;.
..
【输出】输出一行,为修睦四件衣服所要的最短时间。
【样例输入】
1213
5
3
243
【样例输出】
20
【问题描绘】光光上了高中,科目增加了。在长假里,光光的老师们都特别严苛,都给他部署了必定
量的作业。
假期里,光光一共有的时间是
k小时。在长假前,老师们一共给光光部署了
n份作
业,第i份作业需要的时间是ti小时。但是因为老师们相互不商议,
所以光光有可能不可以达成老师的
作业。当不可以达成老师的作业时,光光就过后去处老师说明,而后被老师责备一顿了事。对于一件作
业,只有2种状况:达成或许不达成(快要达成也算不达成)。假如没达成,遇到责备是理当如此的。
但是,不同的作业对于光光来说,责备的力度是不同的。第
i件作业假如没达成,就要遇到
pi个单位
的责备。多次这样以后,光光想要在长假前就知道他起码会遇到多少个单位的责备。你能帮助他吗?
【输入】:第一行只有一个数字
k,表示光光一共有的时间数;第二
行只有一个数字
n,表示作业数;接下来n行,每行两个数字,分别是
ti和pi,两个数字之间用一个空
格分开。
【输出】输出文件
,该行只有一个数字,代表了光光最少遇到的责备。
【样例输入】
5
3
26
13
47
【样例输出】
6
【数据规模商定】
100%的数据中,k≤100000,ti≤10000,pi≤10000;
30%的数据中,n≤20;
100%的数据中,n≤500;
[/]2006
年OIBH新年赛
【问题描绘】你此刻拿到了很多的礼品,你要把这些礼品放进袋子里。你只有一个最多装下
V体积
物件的袋子,你不可以所有放进去。你也拿不动那么重的东西。你预计你能拿的最大重量为
G。此刻你
认识了每一个物件的完满值、重量和体积,你自然想让袋子中装的物件的完满值总和最大,你又得计
划一下了。
【输入】
第一行:G和V表示最大重量和体积。
第二行:N表示拿到N件礼品。
;.
..
第三到N+2行:每行3个数TiGiVi表示各礼品的完满值、重量和体积
【输出】
输出共一个数,表示可能获取的最大完满值。
【输入输出样例】
输入():
5
22
32
43
3033
输出():
50
【数据范围】
对于20%的数据N,V,G,Ti,Vi,Gi≤10
对于50%的数据N,V,G,Ti,Vi,Gi≤100
对于80%的数据N,V,G,Ti,Vi,Gi≤300
80%到100%的数据是N,V,G,Ti,Vi,Gi≤380的失散随机数据。
较复杂的数轴动规
-同济ACM第1132题
Problem小卡卡终于帮农民John找到了走丢的那一头奶牛,John为了感谢小卡卡,不单告诉了他在
Pascal山脉上可能存在Pascal圣地最大的宝藏,还说要请小卡卡喝牛奶。但是农民John发现他家
里所储蓄的牛奶已经喝光了,所以要暂时给奶牛挤奶。小卡卡实在是太好意了,说要帮农民John一同挤
牛奶。John答应了,他把他的n头奶牛中的n/2头(n是个偶数)分给小卡卡挤,他自己挤剩下的n/2
头奶牛。但是每一头奶牛都有不同的产奶量,农民John为了让小卡卡减少负担,他希望他们两个所挤的
牛奶的总量之差最小。小卡卡得悉了每头奶牛的产奶状况以后很快就解决了这个问题。
Input
测试数据第一行一个整数n,n为偶数且小于100。表示有n头奶牛。
第二行n个整数分别给出每头奶牛的产奶量(产奶量的总和不超出2000)。
Output
输出小卡卡和农民所挤的牛奶量的最小差值。
SampleInput
6
792642
SampleOutput
0
;.
..
从n种币值为a[1..n]的硬币中,任选几个硬币构成价值为V的一堆钱币,问最少需要几个硬币?此中每种硬币的数目没有限制。1<=n<=100,1<=v<=100000,1<=a[i]<=100000
:第一行有两个数v和n;第二行有n个以空格分开的数,表示n个币值.
,该行只有一个数,表示所需的最少硬币数,假如不论如何选用硬币,均
不可以获取币值v,则输出0.
已知第j个企业使用k台机器时,能获取的收益为a[j,k],问如何将m台机器在n个企业中分派,才能
获取最大收益?:
企业号机器数123
1234
2145
最大盈余为6,方案为企业2使用2台,企业1使用1台.
---()
小XC发现垒城堡的时候,假以下边的积木比上面的积木大,那么城堡便不易倒。所以他在垒城堡
的时候老是依据这样的规则。小XC想把自己垒的城堡送给幼儿园里同学们,这样能够增添他的好感度。为了公正起见,他决定把送给每个同学相同高的城堡,这样能够防止同学们为了获取更美丽的城
堡而惹起争吵。但是他发现自己在垒城堡的时候并无早先考虑到这一点。所以他此刻要改造城堡。因为他没有剩余的积木了,他灵光一闪,想出了一个奇妙的改造方案。他决定从每一个城堡中挪去一些积木,使得最后每座城堡都相同高。为了使他的城堡更宏伟,他感觉应当使最后的城堡都尽可能的
高。
任务:请你帮助小XC编一个程序,依据他垒的所有城堡的信息,决定应当移去哪些积木才能获取最正确的成效。
(N<=100),表示一共有几座城堡。
以下N行每行是一系列非负整数,用一个空格分开,按从下往上的次序挨次给出一座城堡中所
有积木的棱长。用-1结束。一座城堡中的积木不超出
100块,每块积木的棱长不超出100。
,表示最后城堡的最大可能的高度。假如找不到适合的方案,则输出
0。
输入样例
2
21–1
321–1
;.
..
输出样例
3
一个生物体的构造能够用“基元”的序列表示,一个“基元"用一些英文字符串表示。对于一个基元集
合P,能够将字符串S看作由n个基元P1,P2,,Pn挨次连结而成的。问题是给定一个字符串S和一个
基元会合P,使S的前缀可由P中的基元构成。求这个前缀的最大长度。基元的长度最大为20,字符中
{A,AB,BBC,CA},字符串为ABACABBCAACCB,则最大长度为10,其详细构成为
ABACABBCAA
2214433311
2001年9月11日,一场突发的灾害将纽约世界贸易中心大厦夷为平川,
灾害。为了纪念“911”事件,。
有N块水晶,每块水晶
有一个高度,他想用这
N块水晶搭建两座有相同高度的塔,使他们成为一座双塔,
块水晶中任取M(1≤M≤N)块来搭建。但是他不知道可否使两座塔有相同的高度
,也不知道假如能
搭建成一座双塔,这座双塔的最大高度是多少。所以他来请你帮忙。
给定水晶的数目
N(1≤N≤100)和每块水晶的高度
Hi(N块水晶高度的总和不超出
2000),你
(两座塔有相同的高度),假如能,则输出所能搭
建的双塔的最大高度,不然输出“Impossible”。
输入的第一行为一个数
N,表示水晶的数目。第二行为
N个数,第i个数表示第i个水晶的高度。
输出仅包含一行,假如能搭成一座双塔,则输出双塔的最大高度,不然输出一个字符串“Impossible”。
样例输入:
5
13452
样例输出:
7
题41。/
;.
..
【问题描绘】河上有一座独木桥
,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子
,
青蛙很厌烦踩在这些石子上。因为桥的长度和青蛙一次跳过的距离都是正整数,我们能够把独木桥上
青蛙可能抵达的点当作数轴上的一串整点:
0,1,,L(此中L是桥的长度)。坐标为0的点表示
桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不断的向终点方向跳跃。一次跳跃的
距离是S到T之间的随意正整数(包含
S,T)。当青蛙跳到或跳过坐标为
L的点时,就算青蛙已经跳
出了独木桥。题目给出独木桥的长度
L,青蛙跳跃的距离范围
S,T,桥上石子的地点。你的任务是确
定青蛙要想过河,最少需要踩到的石子数。
【输入文件】输入文件
L(1<=L<=109
),表示独木桥的长度。第二
行有三个正整数
S,T,M,分别表示青蛙一次跳跃的最小距离
,最大距离,及桥上石子的个数,此中1≤S
≤
T≤10,1≤M
≤100。第三行有M个不同的正整数分别表示这
M个石子在数轴上的地点(数据保证
桥的起点和终点处没有石子)
。所有相邻的整数之间用一个空格分开。
【输出文件】输出文件
,表示青蛙过河最少需要踩到的石子数。
【样例输入】
【样例输出】
【数据规模】
10
2
对于30%的数据,L<=10000;
235
对于所有的数据,L<=109。
23567
5
B(9,5)
线性动规
4
北
3
2
题22。1997年普及组第3
题---街道路径条数
1
56
78
9
东
A(1,1)1234
【问题描绘】
设有一个N*M(l≤N≤50,l≤M≤50)的街道(如右图):
规定行人从A(1,1)出发,在街道上只好向东或向北方向行
走。如图,从(1,1)点出发,至(3,3)点,共有6条不同的路径:
(1,1)-(2,1)-(3,1)-(3,2)-(3,3);(1,1)-(2,1)-(2,2)-(3,2)-(3,3)
;(1,1)-(2,1)-(2,2)-(2,3)-(3,3)
;
(1,1)-(1,2)-(2,2)-(3,2)-(3,3);
(1,1)-(1,2)-(2,2)-(2,3)-(3,3);(1,1)-(1,2)-(1,3)-(2,3)-(3,3)
;若在N*M的街道中,设置一个矩形阻碍地区
(包
括围住该地区的街道
)不让行人通行,如图顶用暗影线表示的部分。此矩形阻碍地区能够用
2对极点坐
标给出,如上图中的阻碍地区以
2对极点坐标(2,2),(8,4)表示。此时,从A(1,1)
出发至
B(9,5),只有两条路
径:
路径一:(1,1)-(2,1)-(3,1)-(4,1)-(5,1)-(6,1)-(7,1)-(8,1)-(9,1)-(9,2)-(9,3)-(9,4)-(9,5)
路径二:(1,1)-(1,2)-(1,3)-(1,4)-(1,5)-(2,5)-(3,5)-(4,5)-(5,5)-(6,5)-(7,5)-(8,5)-(9,5)
程序要求:任务一:给出
N,M后,求出所有从(1,1)出发抵达(N,M)的路径的条数。
任务二:给出N,M,同时再给出此街道中的矩形阻碍地区的
2对极点坐标(X1,Y1),(X2,Y2),
而后求出此
种状况下所有从(1,1)出发抵达(N,M)的路径的条数。
【输入格式】输入文件
,1代表任务一,2代表任务二。
1)任务一:第二行有两个数字
,表示N和M
2)任务二:第二行有两个数字
,表示N和M;
第三行有两个数字
,表示矩形阻碍的左下角坐标;
第四行有两个数字
,表示矩形阻碍的右上角坐标;
【输出格式】输出文件
,表示求得的路径条数。
;.
..
【输入样例1】
1
33
【输出样例1】
6
【输入样例2】
2
5
2
84
【输出样例2】
2
题23。2002年普及组第4题--过河卒
A(0,0)
0
【问题描绘】
0
1
如右图,A点有一个过河卒,需要走到目标B点。卒行走规则
:能够
2
向下、或许向右。同时在棋盘上的某一点有一个对方的马
(如上图的
C
3
点),该马所在的点和所有跳跃一步可达的点称为马的控制点。比如右
4
Y
图C点上的马能够控制9个点(图中的P1,P2,,P8和C)。卒不可以经过
对方马的控制点。棋盘用坐标表示
,A点坐标为(0,0)、B点坐标为(n,m)
1
2
3
4
5
6
7
8
P5
P4
P6
P3
C
P7
P8
P1
P2
B(4,8)
(n,m为不超出20的整数),相同马的地点坐标是需要给出的(商定点:C≠点A,同时点C≠点B)。此刻
要求你计算出卒从A点抵达B点的路径的条数。
【输入格式】,该行中有4个以空格分开的数,表示B点的坐标和马的坐标
【输出格式】,该行只有一个数,表示求得的路径条数。
【输入样例】
6632
【输出样例】
17
题24。1997年普及组第1题---统计正方形和长方形个数【问题描绘】
设有一个n*m方格的棋盘(1≤m,n≤1000),求出该棋盘中包含多少个正方形、多少个长方形(不包
括正方形)。比如:当n=2,m=3时,正方形的个数有8个;长方形的个数有10个;
【输入格式】,包含2个以逗号分开的数,分别代表n和m
【输出格式】,包含2个以逗号分开的数,分别代表正方形的个数和长
方形的个数。
【输入样例】
2,3
【输出样例】
;.
..
8,10
题25。1997
年提升组第3题-骑士游览
马
【问题描绘】
设有一个n*m的棋盘(2≤n≤50,2≤m≤50),在棋盘上左下角
(1,1)处有一此中国
图1
马的4种走法
象棋马。马走的规则为:(1)马走日字;
(2)马只好向右走。如图
1
所示。
任务1:当n,m输入以后,找出一条从左下角到右上角的路径。若不存在路径
,则输出'NO'
比如,如图2所示,输入:n=4,m=4,则输出路径:(1,1)-(2,3)-(4,4)(
不独一)
y
10
任务2:当n,m给出以后,同时给出马起点的地点和终点的地点
,试找出从
9
起点到终点的所有路径的数目。如图
3
所示,给出马的起点坐标为
(1,8),终
8
点坐标为(3,8),则有2条路径。
图3:
马从(1,8)至
7
【输入格式】
(3,8)有2条路径
6
,第一行只有一个数字
,1代表任务
1,2代表任务2。
5
1)任务1:第2
行有两个数,表示右上角坐标(n,m)
4
2)任务2:第2
行有两个数,表示右上角坐标(n,m)
3
图2:马从(1,1)至
第3
行有两个数
,表示起点坐标(x1,y1)
2
(4,4)的一条路径
第4
行有两个数
,表示终点坐标(x2,y2)
1
【输出格式】
1
23
4
X
。1)任务1:输出一条路径。
2)任务2:输出一个数,表示路径数。
【输入样例
1】
【输出样例
1】
1
(1,1)-(2,3)-(4,4)
44
【输入样例
2】
【输出样例
2】
2
2
10
8
8
题26。2000
年提升组第4题--方格取数
【问题描绘】
A点0
0
0
0
0
0
0
0
设有N*N
的方格图(N<=30,我们将此中的某些方格中填入正整数,
0
0
13
0
0
6
0
0
而其余的方格中则放入数字
0。如右图所示,表示样例数据的状况.
0
0
0
0
7
0
0
0
某人从图的左上角的
A点出发,能够向下行走,也能够向右走,直到
0
0
0
14
0
0
0
0
抵达右下角的
B点。在走过的路上,他能够取走方格中的数(取走后的
0
21
0
0
0
4
0
0
0
0
15
0
0
0
0
0
0
14
0
0
0
0
0
0
B点
;.
0
0
0
0
0
0
0
0
..
方格中将变为数字0)。这人从A点到B
点共走两次,试找出2条这样
的路径,使得获得的数之和为最大。
【输入格式】输入文件
N(表示N*N
的方格图),
接下来的每行有三个整数,前两个表示地点,第三个数为该地点上所放的数。一行独自的
0
表示输入结
束
【输出格式】输出文件
,该行只有一个数字,表示2条路径上获得的最大的和。
【输入样例】
【输出样例】
8
67
2313
266
357
4414
5221
564
6315
7214
000
题27。NOIP2003
年普及组第3题--栈()
【问题背景】
栈是计算机中经典的数据构造
,简单的说,栈就是限制在一端进行插入删除操作的线性表。栈有两种最
重要的操作,即pop(从栈顶弹出一个元素)和
push(将一个元素进栈)。栈的重要性不言自明,任何
一门数据构造的课程都会介绍栈。宁宁在复****栈的基本观点时,想到了一个书上没有讲过的问题,而
他自己没法给出答案,所以需要你的帮忙。
【问题描绘】
宁宁考虑的是这样一个问题:一个操作数序列,从
1,2,向来到n,栈A的深度大于n。此刻可
以进行两种操作,,从操作数序列的头端移到栈的头端(对应数据构造栈的
push操作)2.
将一个数,从栈的头端移到输出序列的尾端
(对应数据构造栈的
pop操作)使用这两种操作,由一个操
作数序列便可以获取一系列的输出序列。
你的程序将对给定的
n,计算并输出由操作数序列
1,2,,
经过操作可能获取的输出序列的总数。
【输入格式】(1≤n≤18)
【输出格式】,即可能输出序列的总数目
【输入样例】【输出样例】
35
【思虑】
假如1≤n≤3000,如何做?
;.