动态规划习题

动态规划专题分类视图

数轴动规题： ........................................... 1 较复杂的数轴动规 ................................... 4 线性动规 ................................................... 7 区域动规： ............................................. 14 未知的动规： ......................................... 20 数轴动规题：

题1.2001年普及组第4题--装箱问题

【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0

第二行：一个整数，表示物品个数n；接下来n行，分别表示这n个物品的各自体积。 【输出格式】 输出文件box.out只有一行数据，该行只有一个数，表示最小的箱子剩余空间。 【输入样例】 24 6 8 3 12 7 9 7

【输出样例】 0

题2.1996年提高组第4题--砝码秤重 __数据加强版

【问题描述】设有n种砝码,第k种砝码有Ck个,每个重量均为Wk,求：用这些砝码能秤出的不同重量

的个数，但不包括一个砝码也不用的情况。

【输入格式】输入文件weight.in的第一行只有一个数n,表示不同的砝码的种类数.

第2行至第n+1行,每行有两个整数.第k+1行的两个数分别表示第k种砝码的个数和重量. 【输出格式】输出文件weight.out中只有一行数据:Total=N。表示用这些砝码能秤出的不同重量数。 【输入样例】 2 2 2 2 3

【输出样例】 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;

题3.石子归并-szgb.pas

【问题描述】有一堆石头质量分别为W1,W2,?,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。 【输入】输入文件szgb.in的第一行只有一个整数n(1≤n≤50),表示有n堆石子。接下去的n行,为每堆石子质量。

【输出】输出文件szgb.out的只有一行,该行只有一个整数,表示最小的质量差. 【样例输入】 5 5 8 13 27 14

【样例输出】 3

题4.补圣衣

【问题描述】有四个人，每人身上的衣服分别有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)

【输出】输出一行,为修好四件衣服所要的最短时间。 【样例输入】 1 2 1 3 5 4 3 6 2 4 3

【样例输出】 20

题5.光光的作业 homework.pas/homework.exe

【问题描述】光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。 假期里，光光一共有的时间是k小时。在长假前，老师们一共给光光布置了n份作业，第i份作业需 要的时间是ti小时。但是由于老师们互相不商量，因此光光有可能不能完成老师的作业。当不能完成老师的作业时，光光就事后去向老师说明，然后被老师批评一顿了事。对于一件作业，只有2种情况：完成或者不完成（快要完成也算不完成）。如果没完成，受到批评是天经地义的。但是，不同的作业对于光光来说，批评的力度是不同的。第i件作业如果没完成，就要受到pi个单位的批评。多次这样之后，光光想要在长假前就知道他至少会受到多少个单位的批评。你能帮助他吗？ 【输入】输入文件homework.in包含以下内容：第一行只有一个数字k,表示光光一共有的时间数;第二行只有一个数字n,表示作业数;接下来n行，每行两个数字，分别是ti和pi，两个数字之间用一个空格分开。

【输出】输出文件homework.out只包含一行，该行只有一个数字，代表了光光最少受到的批评。 【样例输入】 5 3 2 6 1 3 4 7

【样例输出】 6

【数据规模约定】

100%的数据中,k≤100000,ti≤10000,pi≤10000; 30%的数据中,n≤20; 100%的数据中,n≤500;

题7.打包[pack.pas/pack.c/pack.cpp]2006年OIBH 新年赛

【问题描述】你现在拿到了许多的礼物，你要把这些礼物放进袋子里。你只有一个最多装下V 体积物品的袋子，你不能全部放进去。你也拿不动那么重的东西。你估计你能拿的最大重量为 G。现在你了解了每一个物品的完美值、重量和体积，你当然想让袋子中装的物品的完美值总和最大，你又得计划一下了。 【输入】

第一行：G 和 V 表示最大重量和体积。 第二行：N 表示拿到 N 件礼物。

第三到N+2行：每行3个数 Ti Gi Vi 表示各礼物的完美值、重量和体积 【输出】

输出共一个数，表示可能获得的最大完美值。 【输入输出样例】 输入(pack.in)： 6 5 4 10 2 2 20 3 2 40 4 3 30 3 3

输出(pack.out)： 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 的离散随机数据。

较复杂的数轴动规

题6.挤牛奶-同济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

输出小卡卡和农夫所挤的牛奶量的最小差值。 Sample Input 6

7 9 2 6 4 2 Sample Output 0

题8.一般性的最少硬币组成问题 coinYB.pas/coinYB.exe

从n种币值为a[1..n]的硬币中,任选几个硬币组成价值为V的一堆货币,问最少需要几个硬币?其中每种硬币的数量没有限制。1<=n<=100,1<=v<=100000,1<=a[i]<=100000

输入文件coinYB.in中有两行:第一行有两个数v和n;第二行有n个以空格分隔的数,表示n个币值. 输出文件coinYB.out中只有一行,该行只有一个数,表示所需的最少硬币数, 如果无论如何选取硬币,均不能得到币值v,则输出0.

题9.多个公司间的机器分配问题

已知第j个公司使用k台机器时,能得到的利润为a[j,k],问如何将m台机器在n个公司中分配,才能获得最大利润?要求输出能获得的最大利润及方案.将3台机器分配给2个公司能获得的盈利情况如下： 公司号\\机器数 1 2 1 2 1 2 3 4 3 4 5 最大盈利为6,方案为公司2使用2台,公司1使用1台.

题10.2001年浙江省队选拔---积木城堡castle.pas(castle.exe)

小XC发现垒城堡的时候,如果下面的积木比上面的积木大,那么城堡便不易倒。所以他在垒城堡的时候总是遵循这样的规则。小XC想把自己垒的城堡送给幼儿园里同学们，这样可以增加他的好感度。为了公平起见，他决定把送给每个同学一样高的城堡，这样可以避免同学们为了获得更漂亮的城堡而引起争执。可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了，他灵机一动，想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木，使得最终每座城堡都一样高。为了使他的城堡更雄伟，他觉得应该使最后的城堡都尽可能的高。

任务：请你帮助小XC编一个程序，根据他垒的所有城堡的信息，决定应该移去哪些积木才能获得最佳的效果。

输入文件castle.in 第一行是一个整数N(N<=100)，表示一共有几座城堡。

以下N行每行是一系列非负整数，用一个空格分隔，按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1结束。一座城堡中的积木不超过100块，每块积木的棱长不超过100。

输出文件castle.out 一个整数，表示最后城堡的最大可能的高度。如果找不到合适的方案，则输出0。 输入样例 2

2 1 –1 3 2 1 –1

输出样例 3

题11.生物基元问题

一个生物体的结构可以用“基元”的序列表示,一个“基元\用一些英文字符串表示。对于一个基元集合P,可以将字符串S看作由n个基元P1,P2,?,Pn依次连接而成的。问题是给定一个字符串S和一个基元集合P,使S的前缀可由P中的基元组成。求这个前缀的最大长度。基元的长度最大为20,字符中的长度最大为500000.例如基元集合为{A,AB,BBC,CA },字符串为ABACABBCAACCB,则最大长度为10,其具体组成为

ABACABBCAA

22 144333 11

题12. 双塔

2001年9月11日，一场突发的灾难将纽约世界贸易中心大厦夷为平地，Mr. F曾亲眼目睹了这次灾难。为了纪念“911”事件，Mr. F决定自己用水晶来搭建一座双塔。Mr. F有N块水晶，每块水晶有一个高度，他想用这N块水晶搭建两座有同样高度的塔，使他们成为一座双塔，Mr. F可以从这N块水晶中任取M（1≤M≤N）块来搭建。但是他不知道能否使两座塔有同样的高度,也不知道如果能搭建成一座双塔，这座双塔的最大高度是多少。所以他来请你帮忙。

给定水晶的数量N（1≤N≤100）和每块水晶的高度Hi（N块水晶高度的总和不超过2000），你的任务是判断Mr. F能否用这些水晶搭建成一座双塔（两座塔有同样的高度），如果能，则输出所能搭建的双塔的最大高度，否则输出“Impossible”。

输入的第一行为一个数N，表示水晶的数量。第二行为N个数，第i个数表示第i个水晶的高度。 输出仅包含一行，如果能搭成一座双塔，则输出双塔的最大高度，否则输出一个字符串“Impossible”。 样例输入： 5

1 3 4 5 2 样例输出： 7

题41。过河river.pas/ river.exe/ river.c/ river.cpp

【问题描述】河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，??，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

【输入文件】输入文件river.in的第一行有一个正整数L（1 <= L <= 109），表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数，其中1≤S ≤T≤10,1 ≤M ≤100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

【输出文件】输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。 【样例输入】 【样例输出】 【数据规模】 10 2 对于30%的数据，L <= 10000； 2 3 5 对于全部的数据，L <= 109。 2 3 5 6 7

5 4 B(9,5) 北

线性动规

题22。1997年普及组第3题---街道路径条数 【问题描述】

设有一个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)的路径的条数。

【输入格式】输入文件street.in的第一行只有一个数字,1代表任务一,2代表任务二。 1)任务一：第二行有两个数字,表示N和M 2)任务二：第二行有两个数字,表示N和M； 第三行有两个数字,表示矩形障碍的左下角坐标； 第四行有两个数字,表示矩形障碍的右上角坐标；

【输出格式】输出文件street.out的只有一个数字,表示求得的路径条数。

3 2 1 A(1,1) 1 2 3 4 5 6 7 8 9 东

【输入样例1】 1 3 3

【输出样例1】 6

【输入样例2】 2 9 5 2 2 8 4

【输出样例2】 2

A(0,0) 0 1 2 3 4 5 6 7 8 题23。2002年普及组第4题--过河卒

P4 0 P5 【问题描述】

1 P6 P3 如右图,A 点有一个过河卒,需要走到目标 B 点。卒行走规则:可以 2 C 向下、或者向右。同时在棋盘上的某一点有一个对方的马(如上图的C 3 P2 点),该马所在的点和所有跳跃一步可达的点称为马的控制点。例如右 P7 P8 P B(4,8) 14 Y 图C点上的马可以控制9个点(图中的P1,P2,?,P8和C)。卒不能通过 对方马的控制点。棋盘用坐标表示,A 点坐标为(0,0)、B 点坐标为(n,m)

(n,m为不超过 20 的整数),同样马的位置坐标是需要给出的(约定点:C≠点A,同时点C≠点B)。现在要求你计算出卒从A 点到达 B 点的路径的条数。 【输入格式】输入文件p4.in只有一行数据,该行中有4个以空格分隔的数,表示B点的坐标和马的坐标 【输出格式】输出文件p4.out只有一行数据,该行只有一个数,表示求得的路径条数。 【输入样例】 6 6 3 2 【输出样例】 17

题24。1997年普及组第1题---统计正方形和长方形个数 【问题描述】

设有一个n*m方格的棋盘(1≤m,n≤1000),求出该棋盘中包含多少个正方形、多少个长方形(不包括正方形)。例如：当n=2,m=3时, 正方形的个数有8个；长方形的个数有10个；

【输入格式】输入文件square.in只有一行数据,包含2个以逗号分隔的数,分别代表n和m 【输出格式】输出文件square.out只有一行数据,包含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' y 例如,如图2所示,输入：n=4,m=4,则输出路径：(1,1)-(2,3)-(4,4)(不唯一)

10 任务2：当n,m给出之后,同时给出马起点的位置和终点的位置,试找出从

9 起点到终点的所有路径的数目。如图3所示,给出马的起点坐标为(1,8),终

8 点坐标为(3,8),则有2条路径。 图3: 马从(1,8)至 7 【输入格式】 (3,8)有2条路径 6 从文件horse.in输入,第一行只有一个数字,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 【输出格式】 X 1 2 3 4 输出至文件horse.out中。1)任务1：输出一条路径。2)任务2：输出一个数,表示路径数。 【输入样例1】 【输出样例1】 1 (1,1)-(2,3)-(4,4) 4 4

【输入样例2】 【输出样例2】 2 2 10 10 1 8 3 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 7 0 0 0 而其他的方格中则放入数字0。如右图所示,表示样例数据的情况.

0 0 0 14 0 0 0 0 某人从图的左上角的A 点出发,可以向下行走,也可以向右走,直到

0 21 0 0 0 4 0 0 到达右下角的B点。在走过的路上,他可以取走方格中的数(取走后的

0 0 15 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B点

方格中将变为数字0)。此人从A点到B 点共走两次,试找出2条这样 的路径,使得取得的数之和为最大。

【输入格式】输入文件4.in的第一行为一个整数N(表示N*N的方格图),

接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的0表示输入结束

【输出格式】输出文件4.out中中只有一行数据,该行只有一个数字,表示2条路径上取得的最大的和。 【输入样例】 【输出样例】 8 67 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

题27。NOIP2003年普及组第3题--栈(p2003_3.pas) 【问题背景】

栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。 【问题描述】

宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n，栈A的深度大于n。现在可以进行两种操作，1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）使用这两种操作,由一个操作数序列就可以得到一系列的输出序列。你的程序将对给定的n，计算并输出由操作数序列1，2，?，n经过操作可能得到的输出序列的总数。

【输入格式】输入文件STACK.in只含一个整数n（1≤n≤18）

【输出格式】输出文件STACK.out只有一行，即可能输出序列的总数目 【输入样例】 【输出样例】 3 5 【思考】

如果1≤n≤3000，如何做？

题28。花店橱窗布置问题(IOI99试题)

假设想以最美观的方式布置花店的橱窗,有F束花,每束花的 花瓶1 花瓶2 花瓶3 花瓶4 花瓶5 品种都不一样,同时,至少有同样数量的花瓶被按顺序摆成一行, 杜鹃花 7 23 -5 -24 16 21 -4 10 23 花瓶的位置是固定的,并按从左到右,从1到V顺序编号,V是花 秋海棠 5 5 -4 -20 20 瓶的数目,编号为1的花瓶在最左边,编号为V的花瓶在最右边, 康乃馨 -21 花束可以移动,并且每束花用1到F的整数唯一标志.标志花束的整数决定了花束在花瓶中排列的顺序,即如果i

题29。2007年宁波高中组第3题--宝石 / 1996年提高组第3题--挖地雷 【问题描述】

在一处原始森林中，发现了N个藏有宝石的山洞，这N个山洞以1至N编号。某些山洞间可能会有通道相连，山洞间的通道是单向的，编号较小的山洞可以通过通道走至编号较大的山洞，编号较大的山洞不可以通过通道走至编号较小的山洞。你可以选择任意一个山洞进入，选择一条通道，进入下一个较大编号的山洞，…，最后从某个山洞出来，并获得所有经过的山洞中的宝石。从外面只能进入一次，然后从一个山洞至另一个山洞，直至走出山洞。现在告诉你每个山洞中的宝石数，以及山洞之间的通道情况，求最多能取得多少宝石？

【输入】输入文件gem.in有若干个行数据。

第一行有两个整数n和m，分别表示山洞数和通道数，两数间以一个空格分隔。

第二行有n个整数，第一个数表示第一个山洞的宝石数,第二个数表示第二个山洞的宝石数,…，第n个数表示第n个山洞的宝石数。这n个数间互相以一个空格分隔。

以下m行，每行描述两个山洞间有一条从编号较小山洞通向编号较大山洞的单向通道。每一行的两个整数a和b,可能表示山洞a至山洞b间的单向通道，也可能表示山洞b至山洞a间的单向通道。a和b间有一个空格分隔。

【输出】 输出文件gem.out中只有一行，该行只有一个整数，表示最多能获得的宝石数。 【数据限制】

本题共有10组测试数据，每组10分，共100分， 对于所有的数据，获得的宝石总数不会超过2×109 30%的数据, 1≤n≤1000，0≤m≤10000 100%的数据, 1≤n≤20000，0≤m≤100000

【输入样例】 【输出样例】

5 6 27 10 8 4 7 6 1 3 1 2 1 4 3 4 3 5 4 5

题30。1999提高组第1题-拦截导弹 【问题描述】

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）：1）计算这套系统最多能拦截多少导弹；2）如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 【输入格式】输入文件missile.in只有一行数据,包括若干以空格分隔的正整数,表示来袭的导弹的高度. 【输出格式】输出文件missile.out应包括二行数据。 第一行只有一个正整数,表示最多能拦截的导弹数;

第二行也只有一个正整数,表示要拦截所有导弹最少要配备的系统数。 【输入样例】

389 207 155 300 299 170 158 65 【输出样例】 6 2

题31。2004年提高组第3题-合唱队形

【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2?，K，他们的身高分别为T1，T2，?，TK， 则他们的身高满足T1<...Ti+1>?>TK(1<=i<=K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入格式】输入文件chorus.in有2行数据。第一行是一个整数n(2<=n<=100)，表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

【输出格式】输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

【输入样例】 8

186 186 150 200 160 130 197 220 【输出样例】 4

【数据规模】

对于50％的数据，保证有n<=20； 对于全部的数据，保证有n<=100。

题32。渡河

Problem iRabbit的国家被一条河流(河流是直的)分成南北两岸，南北两岸各有N个城市。北岸的每一个城市有一个唯一的友好城市在南岸，且他们的友好城市彼此不同。为了城市关系的发展，每对城市之间都想要开通轮渡。由于河面上常常有雾。iRabbit决定禁止船只航线相交。以避免发生安全事故。iRabbit希望能在保证安全的情况下，尽可能多地开通航线。由于N非常大（1<=N<=2004），所以必须用程序解决。iRabbit因为备战竞赛，所以十分繁忙，没有时间来编写程序，所以交给手下的TCR和sceoy解决。可是他们两个想了很久都没有想出答案，所以想请你来帮助解决。 Input 输入文件ferry.in的第1行有1个整数：N（1≤N≤2004）。接下来N行,每行两个数A,B。表示这一对友好城市与河源头的距离(不过100000)，其中A代表北岸城市、B代表南岸城市。 Output 输出文件ferry.out中只有一个整数。表示可以开通轮渡的最大线路数。 Sample Input Sample Output 7 4 22 4 2 6 10 3 15 12 9 8 17 17 4 2 a[I] b[I]

题33。最长公共子序列：勇闯黄金十二宫??射手宫-同济ACM第1108题

Problem “已知艾尔里斯和弟弟艾尔里亚的基因基本相同，由于基因表达起来不方便，所以就用n个数字来表示。(因为至今共发现100000种基因，所以每个数字都<=100000)兄弟之间的基因个数是相同的，就是说他们都有n个数字。且对于每个人，这n个数字互不相同。现在要求兄弟之间基因的最长公共部分。可以不连续。”

Input 文件LCS.IN第1行，为n(1<=n<=100000) 下面2行，每行n个数字，表示了一个人的所有基因。

Output文件LCS.OUT一行，为他们两人基因的最长公共部分的长度。

Sample Input Sample Output 7 3 1 2 3 4 5 6 7 7 6 5 4 1 2 3

题38。管状矿藏duct.pas/duct.exe/duct.c/duct.cpp

【问题背景】A公司在南极大陆发现了一个稀有金属矿，该矿沿直线分布，共有n个点，每个点有一定量的矿藏。由于覆盖着冰块，不能从中间开采，只能从两头开采。由于该稀有金属的在地球上存量非常稀少，市场上价格越来越高，已知开采第一天的价格为1，第二天的价格为2，依次类推。A公司决定每天从两头选择一头开采出所有该点的矿藏。 【输入格式】输入文件duct.in包含以下内容：第一行:一个整数n，代表有n个矿点。第二行:n个整数，代表每个矿点的矿藏量。

【输出格式】输出文件duct.out包含一行，该行只有一个整数，代表开采出所有矿藏最多能得到的钱数。

【样例输入】 【样例输出】 4 21 1 2 3 1

【数据规模】

n<=1000，每点矿藏数不超过109，最多能得到的钱数<1012。

区域动规：

题13. 2003年提高组第3题--加分二叉树 【问题描述】

设一个n个节点的二叉树tree的中序遍历为(l,2,3,?,n),其中数字1,2,3,?,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数

若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为（1,2,3,?,n）且加分最高的二叉树tree。要求输出；（1）tree的最高加分（2）tree的前序遍历

【输入格式】文件binary.in

第1行：一个整数n(n＜30)为节点个数。

第2行：n个用空格隔开的整数,为每个节点的分数(分数＜100）。 【输出格式】文件binary.out

第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。 第2行：n个用空格隔开的整数，为该树的前序遍历。 【输入样例】 5

5 7 1 2 10

【输出样例】 145 3 1 2 4 5

题14。2000年普及组第3题--乘积最大 问题描述：

今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生 诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友XZ也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：312， 当N=3，K=1时会有以下两种分法： 1) 3*12=36 2) 31*2=62 这时，符合题目要求的结果是：31*2=62 现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。 输入共有两行：

第一行共有2个自然数N，K（6≤N≤40，1≤K≤6） 第二行是一个长度为N的数字串。 输出所求得的最大乘积（一个自然数）。 样例输入 4 2 1231 样例输出 62

题15。NOIP2003年普及组第2题--数字游戏（p2003_2.pas) 【问题描述】

丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加, 相加所得的m个结果对10取模后再相乘,最终得到一个数k。游戏的要求是使你所得的k最大或者最小。例如,对于下面这圈数字（n=4，m=2）： 2 当要求最小值时,((2-1) mod 10)×((4+3) mod 10)=1×7=7,要求最大值时,为 ((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是,无论是负数还 -1 4 是正数,对10取模的结果均为非负值。丁丁请你编写程序帮他赢得这个游戏。

-【输入】

1 3

输入文件GAME.in第一行有两个整数，n（1≤n≤50）和m（1≤m≤9）。

以下n行每行有个整数,其绝对值不大于104,按顺序给出圈中的数字,首尾相接。

【输出】输出文件GAME.out有两行,各包含一个非负整数。第一行是你程序得到的最小值，第二行是最大值。 【输入样例】

4 2 4 3 -1 2

【输出样例】 7 81

题16。NOIP2001年提高组第3题--统计单词个数(t2001_3.pas) 问题描述

给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个)。要求将此字母串分成k份(1

输入：输入数据放在文本文件input3.dat中，其格式如下：第一行有二个正整数(p，k),表示输入字串有p行;分为k个部分。接下来的p行，每行均有20个字符。再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)接下来的s行，每行均有一个单词。

输出：输出文件output3.dat中只有一行,该行只有一个整数,表示得到的最多单词个数。 样例输入： 1 3

thisisabookyouareaoh 4 is a ok sab

样例输出 7

题17。多边形的三角划分

N个顶点的凸多边形，各顶点权值已知，要求划分成N-2个三角形，使各三角形顶点权值乘积之和为最小

如右图当n=4，各顶点的权值 10 6 分别为10,5,7,6时，所求最小 值为10*5*6+5*6*7=510。 5 7 输入：

第一行：一个整数n

第二行：n个整数,依次表示各顶点的权值

题18。二叉树数

求由n个结点构成的不同的二叉树数. 样例输入: 3

样例输出: 5

题19。石子合并--NOI1995 stone.pas/stone.cpp/stone.c/stone.exe

有n堆石子围成一个圆圈。现在需要把它们合并成一堆石子。每次合并时，只能合并相邻的两堆石子，所耗力气为两堆石子重量之和，合并得到的新堆的重量为原两堆重量之和。问最少需要耗费多少力气？

输入文件stone.in中：第一行一个整数n，第二行n个整数，表示顺序排列的每堆石子的重量。 输出文件stone.out中：只有一行，该行只有一个整数，表示合并这n堆石子最少需要耗费的力气。 数据规模：1<=n<=200，合并n堆石子最少需要耗费的力气不超过2*109。 样例输入； 3 1 3 5

样例输出： 13

题20。1的最优操作序列

(请考虑使用动态规划和其它方法解决此题)

在黑板上写了N（n≤10000）个1，进行如下操作：每次擦去其中两个数a、b，并写上数a*b+1，如此下去直至最后一个数A。 请你编程序求出A的最大值。 输入文件bestone.in中只有一个整数N；

输出文件bestone.out中也只有一个整数,表示得到的最大值 样例输入 5

样例输出 7

题21。NOI2001上海选拔---排序工作量之新任务 问题描述

假设我们将序列中第i件物品的参数定义为Ai，那么排序就是指将A1,?,An从小到大排序。若iAj，则就为一个“逆序对”。SORT公司是一个专门为用户提供排序服务的公司，他们的收费标准就是被要求排序物品的“逆序对”的个数，简称“逆序数”。Grant是这家公司的排序员，他想知道对于n个参数都不同的物品组成的序列集合中，逆序对数为t的物品序列有多少个，并试给出其中一个最小的物品序列。所谓 最小，即若有两个物品序列(A1,A2,?,An)，(B1,B2,?,Bn),存在1≤i≤n,使得(A1,A2,?,Ai-1)＝(B1,B2,?,Bi-1)且Ai＜Bi。

输入：输入文件newsort.in中只有一行，该行只有两个整数n和t (1≤n≤20，0≤t≤n*(n-1)/2 )。 输出：输出文件newsort.out中有二行，第一行只有一个数,表示n个参数都不同的物品组成的序列集合中,逆序数为t的序列个数；第二行是所求物品参数序列。假设n个物品的参数分别为1到n。 样例输入 4 3 样例输出 6

1 4 3 2

题39。能量项链energy.pas/ energy.exe/ energy.c/ energy.cpp

【问题描述】在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为 （Mars单位），新产生的珠子的头标记为m，尾标记为n。

需要时,Mars人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：(4⊕1)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。

【输入文件】输入文件energy.in的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数,所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i

【输出文件】输出文件energy.out只有一行，是一个正整数E（E≤2.1*109），为一个最优聚合顺序所释放的总能量。 【输入样例】 【输出样例】 4 710 2 3 5 10

题40。金明的预算方案budget.pas/budget.exe/budget.c/budget.cpp

主件 附件 【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自

电脑 打印机，扫描仪 己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：\你的房间需要购买哪些 书柜 图书 物品，怎么布置，你说了算，只要不超过N元钱就行\。今天一早，金明就开始做预

书桌 台灯，文具 算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，右表就是

工作椅 无 一些主件与附件的例子：

如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，??，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+ ?+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。 【输入文件】输入文件budget.in 的第1行，为两个正整数，用一个空格隔开：N m（其中N（<32000）表示总钱数，m（<60）为希望购买物品的个数。） 从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v p q（其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）

【输出文件】输出文件budget.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。 【输入样例】 【输出样例】 1000 5 2200 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0

题51 关路灯 【问题描述】

某一村庄在一条路线上安装了n盏路灯，每盏灯的功率（单位时间的耗电量）有大有小。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为，先算一下左边路灯的总功率，再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，这样可以最省电。而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。

现在已知老张走的速度为1米/秒；每个路灯的位置（是一个整数，即距路线起点的距离，单位：米）；以及功率（W），老张关灯所用的时间很短而可以忽略不计。

请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。

【样例输入】 【样例输出】 【输入】输入文件power.in中有若干行。

5 3 270 第1行是两个数字n和c，分别表示路灯数和老张所处位置的路灯号； 2 10 {此时关灯顺第2行至第n+1行，每行有两个整数。其中第k+1行的第一个整数 3 20 序为34215，表示第k盏灯离路线起点的距离，第二个整数表示第k盏灯的功率。 5 20 不必输出这以上n+1行中，每行的两个整数之间都有一个空格分隔。

6 30 个关灯顺序} 【输出】输出文件power.out只有一行，该行只有一个整数，表示 8 10 求得的最少耗电量。(单位：J，1J＝1W·秒)。

【数据限制】本题共有10组测试数据，每组10分，共100分。 30%的数据, 1≤n≤20 【样例说明】有5盏灯，老张从第3100%的数据, 1≤n≤1000 盏灯开始关灯，最小耗电量 8

100%的数据, 求得的最小耗电量不大于1×10 =1*30+4*20+5*10+11*10=270

未知的动规：

题34。Tom的烦恼

Problem Tom是一个非常有创业精神的人,由于大学学的是汽车制造专业,所以毕业后他用有限的资金开了一家汽车零件加工厂 专门为汽车制造商制造零件。由于资金有限他只能先购买一台加工机器。现在他却遇到了麻烦,多家汽车制造商需要他加工一些不同零件(由于厂家和零件不同,所以给的加工费也不同）,而且不同厂家对于不同零件的加工时间要求不同(有些加工时间要求甚至是冲突的,但开始和结束时间相同不算冲突）。Tom当然希望能把所有的零件都加工完,以得到更多的加工费,但当一些零件的加工时间要求有冲突时,在某个时间内他只能选择某种零件加工(因为他只有一台机器),为了赚得尽量多的加工费,Tom不知如何进行取舍。现在请你帮Tom设计一个程序,合理选择部分(或全部)零件进行加工,使得得到最大的加工费。

Input文件tom.in第一行是一个整数n(n<=30000)，表示共有n个零件须加工。接下来的n行中，每行有3个整数，分别表示每个零件加工的时间要求。第一个表示开始时间,第二个表示该零件加工的结束时间,第三个表示加工该零件可以得到的加工费。注：数据中的每个数值不会超过100000. Output文件tom.out中只有一个整数，表示Tom可以得到的最大加工费。

Sample Input Sample Output 3 30 1 3 10 4 6 20 2 5 25

题35。Pascal山脉

Problem 小卡卡顺着老者所指的方向,来到了Pascal神峰的顶峰。老者告诉小卡卡,Pascal山脉有很多座山, 都排在一条直线上,每座山都有不同的高度。Pascal山的山顶有一个神奇的洞穴,进入这个洞穴后,你将会到达这座山前方的另一座山,更加神奇的是,你到达的山一定比他所在的山高度要小。而Pascal圣地最大的宝藏就藏在某一座Pascal山上的洞穴中,这个洞穴的特点是它有一道石门封闭着。小卡卡很想知道进入每座山的洞穴后,他所到达的不同的山会有多少种可能。

Input 第一行一个整数n,表示山的个数.(1<=n<=20000) 第二行有n个整数，从前到后给出每座山的高度。另外两座山可以有相同的高度. (1<=每座山的高度<=maxlongint)

Output共一行n个整数，互相以一个空格分隔。.第i个整数表示他进入第i号山的洞穴后能够到达的不同的山的个数.

Sample Input Sample Output 5 0 1 2 3 4 1 2 3 4 5

题36。光荣的梦想

Problem 依次给出n个整数序列，每次只能交换相邻两个数，问最少需要交换几次才能使整个序列有序。

Input第一行为数列中数的个数n<= 10000,第二行为n个数。表示当前数列的状态。 Output输出一个整数，表示最少需要交换几次能达到升序状态。 Sample Input Sample Output 4 2 2 1 4 3

题37。象形文字hie.pas/hie.exe

【题目描述】光光回到家，完成了双休日的作业，就开始看书，光光对历史非常感兴趣，于是光光就开始看一本古印度的书。书上面印了很多的象形文字，为了叙述简便，我们把每一种形状的象形文字抽象成为一个1到70的数字，比如有这么一串文字：1 27 50 27 29,光光好像看出了什么,觉得如果添加上若干个文字之后，就能够成为一个回文的一句话。比如上面一句话最少需要添加两个字才能变为回文的一句话。添加方法分别为：

（1）方法1：1 29 27 50 27 29 1,或 （2）方法2：29 1 27 50 27 1 29

我们可以知道，给定一句话，通过添加若干个字符是可以成为一个回文句子的。因此，光光需要知道，他最少需要添加多少个文字，才能使这句话变成回文的?

【输入格式】输入文件hie.in包含以下内容：第一行:一个数字n，代表原句有n个字符。第二行:n个数字，代表这句话的内容。

【输出格式】输出文件hie.out包含一行，代表了最少添加文字的个数。 【样例输入】 【样例输出】 5 2 1 27 50 27 29 【数据规模】

30%的数据中，n<=200; 100%的数据中，n<=5000;

题42。[Sense of Beauty] http://acm.timus.ru/problem.aspx?space=1&num=1501 【问题描述】有两堆卡片，每堆卡片有n（4≤n≤1000）张，所有卡片中有n张是红色的，n张是蓝色的。现在要将卡片逐张取下，红的放在一起，蓝的放在一起，每堆卡片中只能取最上面的那张，且要求任意时刻，已取得的红色卡片数和蓝色卡片数相差不超过1张，问如何取，才能完成任务？ 【输入】第一行一个整数n，表示每堆卡片的张数。第二行有n个字符，表示第一堆的卡片颜色，第三行有n个字符，表示第二堆的卡片颜色。其中0代表红色，1代表蓝色，每行的第1个字符代表最上面的卡片颜色，第n个字符代表最下面的卡片颜色。

【输出】一行共2n个字符，表示一种取卡片的方案，如果有多种可行方案，只要输出任意一种即可。其中字符1代表取自第一堆，字符2代表取自第二堆。如果不存在可行方案，则输出一行“Impossible”。 【样例输入1】 4 0011 0110

【样例输出1】 22121112

【样例输入2】 4 1100 1100

【样例输出2】 Impossible

题43。[Fiscal operations] http://acm.timus.ru/problem.aspx?space=1&num=1511 【问题描述】有三个整数A、B、C，1≤A≤101000，1≤B≤101000，1≤C≤101000），如何改变A、B、

C的某些位，使得A+B=C？改变一个数的某位的代价，为该位改变前后数字的差的绝对值。最终的代价为所有位的代价之和。你不能使三个数中的任一个减少位数（使最高位变0），也不能增加位数（在最高位前增加若干位）。

【输入】第一行一个整数A（1≤A≤101000），第二行一个整数B（1≤B≤101000），第三行一个整数C（1≤C≤101000）。

【输出】一个整数，表示最小代价。如果无论怎样改变，A+B都不能等于C，则输出“-1”。 【样例输入】 123 554 345

【样例输出】 8

【样例说明】

可以将A变为121，代价2，将B变为324， 代价5，将C变为445，代价1，总代价为8。

题44。[K-inversions] http://acm.timus.ru/problem.aspx?space=1&num=1523 【问题描述】给出一个排列a1,a2,…,an（所有的ai均为1至n之间的互不相同的整数）。如果1≤i1ai2>…>aik，则将ai1,ai2,…,aik称为长度为k的递减子序列。求排列a1,a2,…,an中长度为k的递减子序列数。

【输入】第一行二个正整数n和k，互相间以一个空格分隔。1≤n≤2000（原题中为20000）， 2≤k≤10。第二行有n个整数，表示给出的一个排列。

【输出】一个整数，表示长度为K的递减子序列数除以109后的余数。 【样例输入1】 3 2 3 1 2

【样例输出1】 2

【样例输入2】 5 3

5 4 3 2 1

【样例输出2】 10

题45。[Ents] http://acm.timus.ru/problem.aspx?space=1&num=1537 【问题描述】艾尔夫教会一只蚂蚁两个单词。以后，蚂蚁按照以下方法学习单词：

1)艾尔夫已经教过的蚂蚁会选没有掌握任何单词的一只老蚂蚁和一只年轻蚂蚁，让他们学会自己掌握的所有单词。

2)上一步学习过的蚂蚁中，艾尔夫教会老蚂蚁一个新单词，教会年轻蚂蚁的单词数等于它已经掌握的单词数。

3)艾尔夫教过的蚂蚁，不能再进一步学习新的单词。

蚂蚁的数量有足够多，请问有多少只蚂蚁掌握了K个单词？

【输入】第一行二个正整数K和P，互相间以一个空格分隔。K≤107， P≤109。 【输出】一个整数，表示掌握K个单词的蚂蚁数量除以P的余数。 【样例输入】 4 10

【样例输出】 2

题46。[Martian army] http://acm.timus.ru/problem.aspx?space=1&num=1472

【问题描述】有n个点，连成一棵树，每个节点处有一个权值，树根为1号点，权值为1，树叶处权值为0，其余点处的权值为一些未知的实数。除了树根外，所有点的父结点编号小于该点的编号。树中每条边有一个权值。比如，权值为Aij连接点I和点j，点I和点j处的权值分别为Bi和Bj，则在边ij处能得到一个乘积|Bi-Bj|*Aij（与边相连的两点处权值之差的绝对值，乘上边上的权值），求如何安排各点处的值，使所有边上乘积之和最小。 【输入】第一行一个整数n（2≤n≤100000）。第二行起至n行共n-1行，每行有二个整数。第i行的二个整数Ki和Ci，表示第i点的父结点为Ki点，i与Ki间的边上的权值为Ci。（1≤Ki

【输出】一个整数，表示求得的最小值（保留两位小数）。 【样例输入】 7 1 10 2 5 2 3 3 1 3 2 3 3

【样例输出】 8.00

题47。[E-mail] http://acm.timus.ru/problem.aspx?space=1&num=1577

【问题描述】已知两个由小写英文构成的字符串A和B，求长度最小的字符串C，使得A和B均为C的子串。

【输入】二行，每行一个字符串，表示原串A和B。

【输出】一个整数，表示长度最小的符合条件的字符串的个数，要求输出所求得值除以109 + 7后的值。

【样例输入1】 b ab

【样例输出1】 1

【样例输入2】 abcab cba

【样例输出2】 4

【提示】样例2的情况时，所求的最小字符串长度为4，共5个字符串，它们为abcaba或abcbab或 acbcab或 cabcab

题48。[Eating High] http://acm.timus.ru/problem.aspx?space=1&num=1570

【问题描述】你和你的朋友共m个人去餐厅吃饭，餐厅中共有n种食品，每种食品能填饱不同数量的肚子，当然每种食品的价格也是不同的。你想让你们所有人都吃饱，又想花费最少的钱。 【输入】第一行只有两个整数N和M。N表示食品数，M表示就餐人数。(1 ≤ N ≤ 100; 1 ≤ M ≤ 20)

以下N行描述N种食品。其中第k+1行有以两个空格分隔的数据Sk Pk Nk，它们分别表示第k种食品：名称为Sk（1至30个的小写英文字母），价格为Pk（1至10000之间），每个能填饱Nk个人的肚子（Nk在0.1至10.0之间，最多三位小数）。 【输出】第一行一个整数，表示最少的钱数。

第二行起的若干行表示最少钱数时的订单，每行表示订制的一种食品，包括食品名称和食品份数，互相间以一个空格分隔。相同的食品不能放在不同行输出，如果有多种方案，则输出食品数最多的一种方案即可。 【样例输入】 4 6

pizza 320 2.4 turkey 1050 3.5 lasagna 150 0.9 pasta 75 0.45 【样例输出】 865 pizza 2 lasagna 1 pasta 1

题49。[三素数数] http://acm.timus.ru/problem.aspx?space=1&num=1586 【问题描述】如果一个数的所有连续三位数字都是大于100的素数，则该数称为三素数数。比如113797是一个6位的三素数数。

【输入】一个整数n（3 ≤ n ≤ 10000），表示三素数数的位数。

【输出】一个整数，表示n位三素数的个数m，要求输出m除以109 + 9的余数。

题50。矿工配餐 IOI2007 Day2第1题

现有两个煤矿，每个煤矿都雇用一组矿工。采煤工作很辛苦，所以矿工们需要良好饮食。每当一辆食品车到达煤矿时，矿工们便会产出一定数量的煤。有三种类型的食品车：肉车，鱼车和面包车。 矿工们喜欢变化的食谱。如果提供的食品能够不断变化，他们的产煤量将会增加。每当一个新的食品车到达煤矿时，矿工们就会比较这种新的食品和前两次（或者少于两次，如果前面运送食品的次数不足两次）的食品，并且：

如果这几次食品车都是同一类型的食品，则矿工们产出一个单位的煤。

如果这几次食品车中有两种不同类型的食品，则矿工们产出两个单位的煤。 如果这几次食品车中有三种不同类型的食品，则矿工们产出三个单位的煤。

预先已知食品车的类型及其被配送的顺序。通过确定哪车食品送到哪个煤矿可以影响产煤量。食品车不能被拆分，每个食品车必须被全部送到一个或另一个煤矿。两个煤矿也并不要求接收相同数量的食品车（事实上，也允许将所有食品车都送到一个煤矿）。

任务

给出食品车的类型及其被配送的顺序，要求你写一个程序，确定哪个食品车应被送到煤矿1，哪个食品车应被送到煤矿2，以使得两个煤矿的产煤量的总和最大。

输入

输入的第一行包含一个整数N (1 ≤ N ≤ 100 000), 表示食品车的数目。

第二行包含一个由N个字符组成的字符串，按照配送顺序依次表示食品车配送的食品的类型。每个字符是以下三个大写字母之一：'M' (表示肉类), 'F' (表示鱼类) 或 'B' (表示面包)。

输出

输出一个整数，表示最大的总产煤量。

评分

在45分的测试数据中，食品车的数目至多为20。

提交时的反馈细节

在竞赛中，对于这个题目，你可以选择至多10次提交在部分正式测试数据上进行测评。测评结束后，可以从竞赛系统中得到关于测试结果的总结。

样例

Input input 6 16 MBMFFB MMBMBBBBMMMMMBMB output output 12 29 在左边的例子中，可以按照如下的顺序运送食品车：煤矿 1, 煤矿 1, 煤矿 2, 煤矿 2, 煤矿 1, 煤矿 2, 依次产生的产煤量为1, 2, 1, 2, 3 和 3 个单位，一共是12 个单位。还有其它运送方式也能产生上述最大总和的产煤量。 （王宏译，李文新校）

如果这几次食品车中有两种不同类型的食品，则矿工们产出两个单位的煤。 如果这几次食品车中有三种不同类型的食品，则矿工们产出三个单位的煤。

预先已知食品车的类型及其被配送的顺序。通过确定哪车食品送到哪个煤矿可以影响产煤量。食品车不能被拆分，每个食品车必须被全部送到一个或另一个煤矿。两个煤矿也并不要求接收相同数量的食品车（事实上，也允许将所有食品车都送到一个煤矿）。

任务

给出食品车的类型及其被配送的顺序，要求你写一个程序，确定哪个食品车应被送到煤矿1，哪个食品车应被送到煤矿2，以使得两个煤矿的产煤量的总和最大。

输入

输入的第一行包含一个整数N (1 ≤ N ≤ 100 000), 表示食品车的数目。

第二行包含一个由N个字符组成的字符串，按照配送顺序依次表示食品车配送的食品的类型。每个字符是以下三个大写字母之一：'M' (表示肉类), 'F' (表示鱼类) 或 'B' (表示面包)。

输出

输出一个整数，表示最大的总产煤量。

评分

在45分的测试数据中，食品车的数目至多为20。

提交时的反馈细节

在竞赛中，对于这个题目，你可以选择至多10次提交在部分正式测试数据上进行测评。测评结束后，可以从竞赛系统中得到关于测试结果的总结。

样例

Input input 6 16 MBMFFB MMBMBBBBMMMMMBMB output output 12 29 在左边的例子中，可以按照如下的顺序运送食品车：煤矿 1, 煤矿 1, 煤矿 2, 煤矿 2, 煤矿 1, 煤矿 2, 依次产生的产煤量为1, 2, 1, 2, 3 和 3 个单位，一共是12 个单位。还有其它运送方式也能产生上述最大总和的产煤量。 （王宏译，李文新校）

本文来源：https://www.bwwdw.com/article/ttdw.html