题解 P1412 【经营与开发】
顾z
2018-09-24 15:04:23
# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/)
~~你没有发现两个字里的blog都不一样嘛~~ qwq
题目描述-->[P1412 经营与开发](https://www.luogu.org/problemnew/show/P1412)
## 分析
虽然看到$Rank_1$已经有了解释.
~~但我认为我能BB的更好~~
我还是决定来写一篇题解. qwq
### 列式
根据题意,我们很容易列出式子.(瞎~~j8~~写.
(变量名与题目描述相同.
$a_1 \times w+ (1-0.01 \times k)\times w \times a_2+(1-0.01 \times k)\times w\times(1-0.01\times k)\times a_3+\dots$
其中$(1-0.01 \times k)\times w$代表新的能力值.
提取公因式$w$. (是叫公因式还是公因子?,qwq
**新式子**
$w\times[a_1+ (1-0.01 \times k) \times a_2+(1-0.01 \times k)\times(1-0.01\times k)\times a_3+\dots]$
然后又可以写成这种形式.
$w\times[a_1+ (1-0.01 \times k) \times a_2+(1-0.01 \times k)^2\times a_3+\dots]$
再将$[]$中的式子变形(根据[秦九韶算法](https://baike.baidu.com/item/%E7%A7%A6%E4%B9%9D%E9%9F%B6%E7%AE%97%E6%B3%95/449196).
得到这样的式子
$w\times[a_1+ (1-0.01 \times k) \times (a_2+(1-0.01 \times k)\times a_3+\dots)]$
然后根据秦九韶一直拆下去.
(下面以$k^{'}$代表$(1-0.01\times k)$
所以我们会得到这样的式子.
$w*[a_1+k^{'}\times(a_2+k{'}\times(a_3+k{'}\times (a_4+\dots)))]$
然后写出来好长好长一段 qwq.
### 然后考虑正解**为什么是倒着枚举**?.
显然,我们从$1-n$枚举星球,钻头会受到影响.
即后面的答案会受到影响.(后效性.
而我们从后向前枚举则可以免去这种影响.(感觉这句话自己说的很虚啊.
如果不理解这句话的话,请回想秦九韶算法也是从里到外地求解.
对应到这个题的话我们就相当于从后向前枚举.
因为秦九韶算法的话,从里到外的拆分会乘上$k^{'}$.(钻头能力值会降低.
**简单来讲的话**
我们通过一直乘上$k^{'}$,最里层的式子,对应的就是我们最后一次使用钻头的情况.
同样,次里层的式子,对应的就是我们倒数第二次使用钻头的情况.
(无法正确组织语言. qwq.
如果不懂的话还是用笔试一下.
这样我们**模拟的就是这个从里向外求解的过程**.
所以我们求出来的一定会是我们的答案.
------------------代码-------------------
```cpp
#include<bits/stdc++.h>
#define R register
using namespace std;
int n;
double k,c,w;
struct cod{int idx;double cost;}type[100008];
double ans;
int main()
{
scanf("%d%lf%lf%lf",&n,&k,&c,&w);
k=1-0.01*k;c=1+0.01*c;//我说我式子一开始带错了你信不信 qwq.
for(R int i=1;i<=n;i++)
scanf("%d%lf",&type[i].idx,&type[i].cost);
for(R int i=n;i>=1;i--)
if(type[i].idx==1)ans=max(ans,ans*k+type[i].cost);
else ans=max(ans,ans*c-type[i].cost);
printf("%.2lf",ans*w);
}
```