#2368. 星际贸易

    ID: 2368 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>PROV赛事:contest4095来源:qoj.ac数据:公开样例动态规划

星际贸易

星际贸易

题目描述

第三题:星际贸易(程序文件名:star.exe)100分,运行时限:1s Coke 是一个精明的小商人。这次他想大胆地做一次星际贸易。于是他选定了银河贸易交通 局所给定的一条贸易路线,从地球出发,依次经过 。贸易路线在 结 束(Coke 最后要在 上观光旅游)。 银河系中各个星球实行计划经济。在一个星球上出售商品,必须获得那个星球的许可证。 Coke 手中的许可证允许他在 上出售指定配额量 吨的商品(而且既不能多 也不能少,当然他可以不在 上出售任何商品),出售后能够获得 的收入。 由于Coke 的私人飞船载重有限,这个精明的小商人不得不好好计划一下他应该向哪些星球出售 商品。 飞船采用反物质推进系统行驶,需要反物质燃料。反物质燃料不是用来维持平常飞行的(宇 宙间没有阻力),而是用于飞船从星球出发时加速以及飞船到达星球时减速所需的消耗。每次加 速和减速各消耗一个单位的反物质燃料。 另外,作如此长距离的飞行,飞船显然要在中途停靠并在某些星球上补充反物质燃料以及对 飞船定期进行一些维护(维护只能在星球上进行)。由于各星球之间科技发展水平不等,在各个星 球上反物质燃料的售价以及维护飞船的费用是不同的。 此外,银河贸易交通局正在举办小商人贸易竞赛,对于贸易额(即总贸易收入)得到冠军的商

2005-7-8 人有丰厚的奖赏,因此Coke 决定不惜血本,要使自己的贸易额达到最大。当然,在贸易额最大的 同时,作为一个商人,他还是希望净利润尽可能大(净利润=贸易额-燃料费用-维护费用)。 假设从地球出发时飞船刚刚维护过并装满了燃料,并且飞船每次停靠一个星球出售商品或 补充反物质燃料或在终点站观光旅游时就会在那里做一次维护。Coke 希望你给他制定一个方案, 满足他的要求。 【输入格式】(input.txt) 从文件input.txt 中读入数据,文件的第1 行为4 个正整数 。 表示Coke 这次要行经的星球数, 表示飞船最大的载重量, 表示飞船最多能携带的燃料数。 表示飞船不做维护所能飞行的 最大距离。文件的第 行是对每个星球的描述。其中第 行有5 个非负整数 。 表示从地球依次经过 最后到达 的距离。 为星球 上一个单位反物质的价格,若 为0,则说明这个 星球还没有制造反物质的技术。 表示飞船在 上做维护所需要的费用。 假设输入数据满足:对于 ,一定有 ,并使得只有一种获得最大贸易额的方法。 【输出格式】(output.txt) 如果可以找到这样的方案,那么输出文件output.txt 中包含两个整数X 和Y。X 表示贸易 额,Y 表示净利润并且两个数字之间用一个空格隔开。如果不能完成这次星际贸易,那么输出文 件output.txt 中包含 “Poor Coke!”(不包括引号)。 【输入输出样例1】 input.txt output.txt 6 3 10 4 6 2 1 2 1 1 1 1 2 2 2 1 1 2 3 9 1 1 1 4 0 1 1 1 5 0 1 1 1 6 1 1 【输入输出样例2】 input.txt output.txt 6 3 2 4 Poor Coke! 1 2 1 1 1 1 2 2 2 1 1 2 3 0 1 1 1 4 0 1 1 1 5 0 1 1 1 6 1 1

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

6 3 10 4
1 2 1 1 1
1 2 2 2 1
1 2 3 9 1
1 1 4 0 1
1 1 5 0 1
1 1 6 1 1
6 2

样例 2

6 3 2 4
1 2 1 1 1
1 2 2 2 1
1 2 3 0 1
1 1 4 0 1
1 1 5 0 1
1 1 6 1 1
Poor Coke!