问题 5049 --开采矿物

5049: 开采矿物

题目描述

  小 K 有一把初始能力值为 $w$ 的镐子,他将依次经过 $n$ 个地点。
每个地点分为资源型和维护型两类。假设当前镐子的能力值为 $p$:
资源型:含价值为 $a_i$ 的矿物,若选择开采,则得到 $a_i \times p$ 的金钱,之后镐子的能力值减少 $k\%$,即 $p'=p\times(1-0.01k)$;如果选择不开采,则没有影响。
维护型:可以花一定金钱来维护自己的镐子,维护费用为 $b_i$,若选择维护,则支付 $b_i\times p$ 的金钱,之后镐子的能力值增加 $c\%$,即 $p'=p\times (1+0.01c)$;如果选择不维护,则没有影响。
每个地点至多开采一次或维护一次。
假设小 K 刚开始手上有 $10^{100}$ 的金钱(即不用担心没钱维护镐子),请你帮他最大化净收入(即收入减去支出)。

输入

第一行四个整数 $n,k,c,w$。
以下 $n$ 行,每行 $2$ 个整数 $\mathrm{type},x$:
  $\mathrm{type}=1$ 则代表其为资源型,$x$ 为其矿物价值 $a_i$;
  $\mathrm{type}=2$ 则代表其为维护型,$x$ 为其维护费用 $b_i$;

输出

输出一行一个实数表示答案,保留 $2$ 位小数。

样例输入输出

输入#1 复制
5 50 50 10
1 10
1 20
2 10
2 20
1 30
输出#1 复制
375.00

提示

对于 $30\%$ 的数据,$n \leq 100$;
另有 $20\%$ 的数据,$n \leq 1000, k=100$;
对于 $100\%$ 的数据,$1 \leq n \leq 10^5$,$0 \leq k,c,w,a_i,b_i \leq 100$,保证答案不超过 $10^9$。

序号 标题 作者 发表时间 费用 订购数 操作