动态规划：NOIP的题目(2)

DP Problem Set

输出

输出文件仅一行。如果凑不齐K+3双，输出-1，否则输出长度差平方和的最小值。 样例 CHOP.IN 10 1

1 1 2 3 3 3 4 6 10 20

CHOP.OUT 5 说明

第一双 1 1 第二双 2 3 第三双 3 3 第四双 4 6

(1-1)^2+(2-3)^2+(3-3)^2+(4-6)^2=5

_______________________________________________________________________________

护卫队

源程序名 CONVOY.??? (PAS,C,CPP) 可执行文件名 CONVOY.EXE 输入文件名 CONVOY.IN 输出文件名 CONVOY.OUT

护卫车队在一条单行的街道前排成一队，前面河上是一座单行的桥。因为街道是一条单行道，所以任何车辆都不能超车。桥能承受一个给定的最大承载量。为了控制桥上的交通，桥两边各站一个指挥员。护卫车队被分成几个组，每组中的车辆都能同时通过该桥。当一组车队到达了桥的另一端，该端的指挥员就用电话通知另一端的指挥员，这样下一组车队才能开始通过该桥。每辆车的重量是已知的。任何一组车队的重量之和不能超过桥的最大承重量。被分在同一组的每一辆车都以其最快的速度通过该桥。一组车队通过该桥的时间是用该车队中速度最慢的车通过该桥所需的时间来表示的。问题要求计算出全部护卫车队通过该桥所需的最短时间值。 输入

输入文件第一行包含三个正整数(用空格隔开)，第一个整数表示该桥所能承受的最大载重量(用吨表示)；第二个整数表示该桥的长度(用千米表示)；第三个整数表示该护卫队中车辆的总数(n<1000)。接下来的几行中，每行包含两个正整数W和S(用空格隔开)，W表示该车的重量(用吨表示)，S表示该车过桥能达到的最快速度(用千米/小时表示)。车子的重量和速度是按车子排队等候时的顺序给出的。 输出

输出文件应该是一个实数，四舍五入精确到小数点后1位，表示整个护卫车队通过该

- 6 -

DP Problem Set

桥所需的最短时间(用分钟表示)。 样例

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

_______________________________________________________________________________

DOLLARS

源程序名 DOLLARS.??? (PAS,C,CPP) 可执行文件名 DOLLARS.EXE 输入文件名 DOLLARS.IN 输出文件名 DOLLARS.OUT

在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元，使他从100美元开始，最后能获得最高可能的价值。 输入

输入文件的第一行是一个自然数N，1≤N≤100，表示戴维学习汇率的天数。 接下来的N行中每行是一个自然数A，1≤A≤1000。第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，戴维既能用100美元买A马克也能用A马克购买100美元。 输出

输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元，保留两位小数)。 注意：考虑到实数算术运算中进位的误差，结果在正确结果0.05美元范围内的被认为是正确的，戴维必须在最后一天结束之前将他的钱都换成美元。 样例

DOLLARS.IN 5 400

- 7 -

DP Problem Set

300 500 300 250

DOLLARS.OUT 266.66

样例解释 (无需输出)

Day 1 ... changing 100.0000 美元= 400.0000 马克 Day 2 ... changing 400.0000 马克= 133.3333 美元 Day 3 ... changing 133.3333 美元= 666.6666 马克 Day 5 ... changing 666.6666 马克= 266.6666 美元

_______________________________________________________________________________

动态规划部分

（初中组不作要求）

潜水员

（gas.exe）

潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

3 36 120 10 25 129 5 50 250 1 45 130 4 20 119

如果潜水员需要5升的氧和60升的氮则总重最小为249 （1，2或者4，5号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入格式

从文本文件gas.in中读入数据。

第一行有2整数t，a（1 …… 此处隐藏：337字，全部文档内容请下载后查看。喜欢就下载吧 ……