输入 9 5 8 9 2 3 1 7 4 6 输出 4
护卫队(动态规划)
源程序名 CONVOY.??? (PAS,C,CPP) 输入文件名 CONVOY.IN 输出文件名 CONVOY.OUT
护卫车队在一条单行的街道前排成一队，前面河上是一座单行的桥。因为街道是一条单行道，所以任何车辆都不能超车。桥能承受一个给定的最大承载量。为了控制桥上的交通，桥两边各站一个指挥员。护卫车队被分成几个组，每组中的车辆都能同时通过该桥。当一组车队到达了桥的另一端，该端的指挥员就用电话通知另一端的指挥员，这样下一组车队才能开始通过该桥。每辆车的重量是已知的。任何一组车队的重量之和不能超过桥的最大承重量。被分在同一组的每一辆车都以其最快的速度通过该桥。一组车队通过该桥的时间是用该车队中速度最慢的车通过该桥所需的时间来表示的。问题要求计算出全部护卫车队通过该桥所需的最短时间值。 输入
输入文件第一行包含三个正整数(用空格隔开)，第一个整数表示该桥所能承受的最大载重量(用吨表示)；第二个整数表示该桥的长度(用千米表示)；第三个整数表示该护卫队中车辆的总数(n<1000)。接下来的几行中，每行包含两个正整数W和S(用空格隔开)，W表示该车的重量(用吨表示)，S表示该车过桥能达到的最快速度(用千米/小时表示)。车子的重量和速度是按车子排队等候时的顺序给出的。 输出
输出文件应该是一个实数，四舍五入精确到小数点后1位，表示整个护卫车队通过该桥所需的最短时间(用分钟表示)。 样例
CONVOY.IN
100 5 10 40 25 50 20 50 20 70 10 12 50 9 70 49 30 38 25 27 50 19 70
CONVOY.OUT 75.0
交错匹配（动态规划）
问题描述：
有两行自然数，UP[1..N]，DOWN[1..M]，如果UP[I]=DOWN[J]=K，那么上行的第I个位置的数就可以跟下行的第J个位置的数连一条线，称为一条K匹配，但是同一个位置的数最多只能连一条线。另外，每个K匹配都必须且至多跟一个L匹配相交且K≠L！现在要求一个最大的匹配数。
例如：以下两行数的最大匹配数为8
1 2 3 3 2 4 1 5 1 3 5 10
3 1 2 3 2 4 12 1 5 5 3
输入格式：
从文件CROSS.IN读入数据，第一行有两个正整数N和M。第二行N个UP的自然数，第三行M个DOWN的自然数。其中0 输出格式： 最大匹配数输出到CROSS.OUT。 样例一 CROSS.IN 12 11 1 2 3 3 2 4 1 5 1 3 5 10 3 1 2 3 2 4 12 1 5 5 3 CROSS.OUT 8 样例二 CROSS.IN 4 4 1 1 3 3 1 1 3 3 CROSS.OUT 0 序列（部分和） 给一个数列a1, a2, ?, as和一个正整数n，保证满足0<=ai<=30000（1<=i<=s），并且数列中所有数之和正好等于s+n。 你要做的是检查这个数列{ai}和n是否满足下面的条件： 对于任意的i和j（1<=i<=j<=s），不等式ai+a(i+1)+?+aj<=(j-i+1)+n始终成立。 输入：seq.in 第一行是两个正整数s和n，它们都不超过30000。接下来的s行按顺序给出数列{ai}。 输出：seq.out 满足条件，输出YES；若不满足，输出NO。 样例1 输入 4 3 2 3 0 2 输出 YES 样例2 输入 4 5 1 0 5 3 输出 NO Secret Milking Machine（最短路径） 在一个无向图中，有N个顶点和P条无向边，2<=N<=200，1<=P<=40000。每条边的长度都是正整数，不超过1000000。可能有重边。每条边的一个方向只能被经过一次。 要找出1条从顶点1走到顶点N的路径。 求所有方案中，使用的最长边的最小值。保证有解。 输入：secret.in 第一行是N、P。 接下来的P行，描述每一条边。每行3个整数，前两个表示边连接的顶点编号，第三个数表示这条边的长度。 输出：secret.out 方案中使用的最长边的最小值。 样例： 输入 7 9 1 2 2 2 3 5 3 7 5 1 4 1 4 3 1 4 5 7 5 7 1 1 6 3 6 7 3 输出 3 圆桌会议round (深度优先搜索) N个人开会，1<=N<=10。要安排入圆桌。每个人i有一个等级Hi，要求任何相邻两个人的等级差不能超过K。 问有多少种安排的方法。两种方法如果存在一个人，他左侧的人如果在这两个方法中不同，那么就认为这两种方法不同。（即区分翻转，但是不区分旋转） 输入：round.in 第一行是N和K，1<=K<=1000000。 接下来的N行，每行一个整数，表示每个人的等级Hi，1<=Hi<=1000000。 输出：round.out 一个整数，表示方案总数。 样例： 输入