team2012-D1-sol-0008

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== 题目大意 ===
你是一名赏金猎人, 现在你要依次去 N 座城市猎取赏金. 每座城市都有一个武器店和一个任务(只有一个武器店, 只有一个任务). 每次到一座城市, 你会先去武器店提升攻击力 (当然也可以选择不提升攻击力), 每提升一点攻击力需要 a[i] 的金钱. 你可以购买任意实数数量的攻击力, 只要你的钱够. 然后你会去做任务, 做完任务你会获得 (当前攻击力 * b[i]) 的金钱, 做完任务你会立刻离开这座城市, 不会再去这座城市的武器店. 去第一座城市之前你拥有 X 的金钱和 Y 的攻击力. 求问你最后最多可以拥有多少金钱.

=== 数据范围 ===
 * 0 ≤ N, X, Y ≤ 100000

=== 解题思路 ===
这题我是按照猛犸的解题报告的思路来做的, 做法就是倒过来推. 不过我想推一下不等式验证一下算法的正确性, 但是式子有点复杂, 所以当时推到一半推不下去了, 之后再补证明一下. 应该是需要证明以下几点:
 1. 如果决定在一个地方购买攻击力，那么一定是将钱全部花完
 2. 若最后一次买攻击力的城市是 i, 那么一定有 a[i] >= sum{b[j]|i<=i<=n}.
 3. 若现在在城市 i, 下一次买攻击力的城市是 j, 如果在 i 买攻击力可以使同等条件下在 i 不买攻击力最后所得的金钱更多, 那么就要在 i 买攻击力
前两点很容易可以证明, 第三点需要证明一个不等式成立, 我过两天再去推一下.
 

题目大意

你是一名赏金猎人, 现在你要依次去 N 座城市猎取赏金. 每座城市都有一个武器店和一个任务(只有一个武器店, 只有一个任务). 每次到一座城市, 你会先去武器店提升攻击力 (当然也可以选择不提升攻击力), 每提升一点攻击力需要 a[i] 的金钱. 你可以购买任意实数数量的攻击力, 只要你的钱够. 然后你会去做任务, 做完任务你会获得 (当前攻击力 * b[i]) 的金钱, 做完任务你会立刻离开这座城市, 不会再去这座城市的武器店. 去第一座城市之前你拥有 X 的金钱和 Y 的攻击力. 求问你最后最多可以拥有多少金钱.

数据范围

• 0 ≤ N, X, Y ≤ 100000

解题思路

这题我是按照猛犸的解题报告的思路来做的, 做法就是倒过来推. 不过我想推一下不等式验证一下算法的正确性, 但是式子有点复杂, 所以当时推到一半推不下去了, 之后再补证明一下. 应该是需要证明以下几点:

1. 如果决定在一个地方购买攻击力，那么一定是将钱全部花完

2. 若最后一次买攻击力的城市是 i, 那么一定有 a[i] >= sum{b[j]|i<=i<=n}.

3. 若现在在城市 i, 下一次买攻击力的城市是 j, 如果在 i 买攻击力可以使同等条件下在 i 不买攻击力最后所得的金钱更多, 那么就要在 i 买攻击力

前两点很容易可以证明, 第三点需要证明一个不等式成立, 我过两天再去推一下.