（1） 10≤N≤20000 1≤k≤1000
（2） 1≤A≤B≤N， 0≤C≤N-(B-A+1) 【 样 例 】
标准输入 13 3 6 12 1 2 9 0 10 13 8 6 7 8 9 10 11 12 2 3 4
标准输出 【试题三】
瓷器物流规划
【问题描述】
南方某瓷都有一套较完整的瓷器运输物流系统。该物流系统由若干个物流基站组成，以1?N 进行编号。每个物流基站i 都有且仅有一个后继基站J，而可以有多个前驱基站。基站
i 中需要继续运输的瓷器都将被运往后继基站J，显然一个物流基站的后继基站不能是其本
身。编号为 1 的物流基站称为控制基站，从任何物流基站都可以经过若干次周转将瓷器运往控制基站1。注意控制基站也有后继基站，以便在需要时进行物资的流通。在本瓷器物流系统规划中，高可靠性与低成本是主要设计目的。
对于基站i，我们定义其“可靠性” R(i) 如下：
设物流基站i 有 W 个前驱基站P 1, P 2 ,?. , P W ，即这些基站以i 为后继基站，则基站i 的可靠性R(i)满足下式：
R(i)=Ci + K*[R(P1)+ R(P1)+??+ R(PW)]
其中:Ci 和 k 都是常实数且恒为正，且 0 整个系统的可靠性与控制基站1的可靠性都相关，我们的目标是能否通过修改本瓷器物流系统，（即更改某些基站的后继基站），使得控制基站的可靠性R(1)尽量大。 但由于经费限制，最多只能修改 M 个基站的后继基站，并且，控制基站的后继基站不 可被修改。因而我们所面临的问题就是，如何修改不超过M 个基站的后继，使得控制基站的可靠性R(1)最大化。 【标准输入】 第一行: T 表示以下有T组测试数据（0 头一行包含两个整数与一个实数，N, m, k。其中N 表示基站数目，m 表示最多可修改的后继基站数目，k 分别为可靠性定义中的常数。 下一行包含N 个整数，分别是S1, S2?SN，即每一个基站的后继基站编号。 第三行包含N 个正实数，分别是C1, C2?CN，为可靠性定义中的常数。 【标准输出】 输出有T行，第i行为仅包含一个实数，为第i组测试数据可得到的最大R(1)。精确到小数点两位。 【输入样例】 【输出样例】 1 30.00 4 1 0.5 2 3 1 3 10.0 10.0 10.0 10.0 【样例说明】 ① ① ② ④ ② ④ ③ ③ 原有物流系统如左图所示，4 个物流基站的可靠性依次为22.8571，21.4286， 25.7143，10。 最优方案为将2 号基站的后继基站改为1 号，如右图所示。 此时4 个基站 的可靠性依次为30，25，15，10。 【数据规模和约定】 对于所有的数据，满足 1≤m ≤ N ≤ 60，Ci ≤ 10，0.3 ≤ k < 1，请使用双精度实数，无需考虑由此带来的误差。 6 【试题四】 壮观的瓷器广场 【问题描述】 最近，某瓷都为了体现“千年瓷都” 的风貌，将要建立一个壮观的瓷器广场迎接来 自各国的宾客。，顾问Dr.Kong提出了一项建议：在巨大的广场南面展示N件高度不等的瓷器灯柱。夜间，这些瓷器灯柱逐一闪亮，由低至高，如此场景必将十分的绚丽夺目。 然而，在瓷器灯柱运来安放后，Dr.Kong才发现粗心的工人并没有按照从低到高的顺序安放瓷器灯柱。由于瓷器灯柱已经竖立起来，不可能全部推倒重新安放，人力又搬不动。因此，Dr.Kong只能借助巨型吊车每次将两个瓷器灯柱的位置小心翼翼地进行交换。 例如，有3个瓷器灯柱初始时高度顺序是：3 1 2。可以先用吊车交换后两个灯柱的位置，得到3 2 1，再交换第一和第三个灯柱，得到最终序列1 2 3。 毕竟，用吊车交换灯柱位置可不是一件容易的事情，灯柱越高其重量越大，交换的难度也就越高。Dr.Kong估算出，每一次交换的难度等于交换的两个灯柱的高度的和。而整个交换方案的难度等于每次交换难度的总和。 例如先前的交换方案。原先3 1 2，交换后两个（难度为1+2=3），得到3 2 1，再交换第一和第三个（难度为3+1 = 4），得到1 2 3。因此，该方案的难度为3+4 =7。 为了使交换工作尽快完成，难度最低的交换方案自然是首选了。Dr.Kong虽然知道一些选择，冒泡，归并，快速甚至堆排序等。然而，在该问题面前，这些方法看起来似乎毫无用武之地！你有何办法？ 【标准输入】 第一行: M 表示以下有M组测试数据（0 头一行： N (表示瓷器灯柱的数目1 ≤ N ≤ 100 ) 下一行: H1 H2 ….Hn (表示依次安放灯柱的高度， 1≤Hi≤ 1000，) 【标准输出】 输出有M行，第i行为仅包含一个整数, 为第i组测试数据可得到的交换方案的最低难 度值。 【 样 例 】 标准输入 标准输出 7 103 2 3 3 1 2 4 30 40 10 23 【试题五】 瓷器工艺 古窑是某瓷都最著名的陶瓷历史文化景点，景区内的古工艺、古作坊、古窑房、古建筑，堪称瓷文化风景之“四绝”，在文博旅游资源中，起着举足轻重的作用。 对古瓷器的开发利用，关键是要做“活”，充分挖掘其丰富的文化内涵，让历史与现实对话。但要真正演绎或体现其陶瓷文化内涵，必须全方位恢复以圆器和琢器为典型代表的手工艺作坊全部的传统工艺生产流程，增加其内涵价值。 某瓷器厂准备赶制一批仿古瓷器，参加某国世博会的展览。按照六大要素进行整合设计和规划，要生产出这批高品质的瓷器，需要多项工艺制作过程，每一项工艺都需要一定的时间来完成。当然，有些工艺必须在另一些工艺完成的情况下才能进行。我们把这些工作称为完成本项工艺的前期准备工作。至少有一项工艺制作不需有前期准备工作，这项工作可以最早着手完成的工作，标记为工艺1。 研发科的Dr.Kong接到了一个要完成N个工艺制作的清单，并且这份清单是有一定顺序的，工艺K (k>1)的准备工作只可能在工艺1..k-1中。 你能否帮Dr.Kong写一个程序，计算出所有工艺都被制作完成的最短时间。当然互相没有关系的工艺可以同时工作，并且，你可以假定瓷器厂有足够多的工人来同时完成任意多项工艺的制作任务。 【标准输入】 第1行： N 表示必须要完成的工艺的数目 (3<=N<=500)； 第2 ~ N+1行：每行有一些用1个空格隔开的整数，分别表示： * 工艺序号i (1<=i<=N,)； * 完成本项工作所需要的时间Ti（1<=Ti<=100）； * 一些必须完成的准备工作，总数不超过100个，由0结束。 有些工艺的制作是不需要准备的工作的只描述一个单独的0。 【标准输出】 一个整数，表示完成所有工艺制作需要的最短时间。 【 样 例 】 标准输入 7 1 5 0 2 2 1 0 3 3 2 0 4 6 1 0 5 1 2 4 0 6 8 2 4 0 7 4 3 5 6 0 标准输出 23 【T6】 Faulty Odometer 【Description】 You are given a car odometer which displays the miles traveled as an integer. The odometer has a defect, however: it proceeds from the digit 3 to the digit 5, always skipping over the digit 4. This defect shows up in all positions (the one's, the ten's, the hundred's, etc.). For example, if the odometer displays 15339 and the car travels one mile, odometer reading changes to 15350 (instead of 15340). 【Input】 Each line of input contains a positive integer in the range 1..999999 which represents an odometer reading. (Leading zeros will not appear in the input.) The end of input is indicated by a line containing a single 0. You may assume that no odometer reading will contain the digit 4. 【Output】 Each line of input will produce exactly one line of output, which will contain: the odometer reading from the input, a colon, one blank space, and the actual number of miles traveled by the car. 【Sample Input】 15 250 0 【Sample output】 15: 13 250: 198