luogu#P1412. 经营与开发

    ID: 5470 Type: RemoteJudge 1000ms 125MiB Tried: 4 Accepted: 3 Difficulty: 5 Uploaded By: Tags>动态规划dp福建省历届夏令营

经营与开发

题目描述

4X4X 概念体系,是指在 PC 战略游戏中一种相当普及和成熟的系统概念,得名自 44 个同样以 EX 为开头的英语单词。

  • eXplore\verb!eXplore!(探索)
  • eXpand\verb!eXpand!(拓张与发展)
  • eXploit\verb!eXploit!(经营与开发)
  • eXterminate\verb!eXterminate!(征服)

——维基百科

今次我们着重考虑 exploit 部分,并将其模型简化:

你驾驶着一台带有钻头(初始能力值 ww)的飞船,按既定路线依次飞过 nn 个星球。星球笼统的分为 22 类:资源型和维修型。(pp 为钻头当前能力值)

  1. 资源型:含矿物质量 aia_i,若选择开采,则得到 ai×pa_i\times p 的金钱,之后钻头损耗 k%k\%,即 pp×(10.01k)p\gets p\times (1-0.01k)
  2. 维修型:维护费用 bib_i,若选择维修,则支付 bi×pb_i\times p 的金钱,之后钻头修复 c%c\%,即 pp×(1+0.01c)p\gets p\times (1+0.01c)

注:维修后钻头的能力值可以超过初始值(你可以认为是翻修 + 升级)

金钱可以透支。

请作为舰长的你仔细抉择以最大化收入。

输入格式

第一行 44 个整数 n,k,c,wn,k,c,w

以下 nn 行,每行 22 个整数 type,x\mathrm{type},x

  • type\mathrm{type}11 则代表其为资源型星球,xx 为其矿物质含量 aia_i
  • type\mathrm{type}22 则代表其为维修型星球,xx 为其维护费用 bib_i

输出格式

一个实数(保留 22 位小数),表示最大的收入。

5 50 50 10
1 10
1 20
2 10
2 20
1 30

375.00

提示

数据范围及约定

  • 对于 30%30\% 的数据 n100n \le 100
  • 另有 20%20\% 的数据 n1000n \le 1000k=100k=100
  • 对于 100%100\% 的数据 n100000n \le 1000000k,c,w,ai,bi1000 \le k,c,w,a_i,b_i \le 100,保证答案不超过 10910^9