题解 P1412 【经营与开发】

2018-09-24 15:04:23


z

你没有发现两个字里的blog都不一样嘛 qwq

题目描述-->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]$

再将 $[]$ 中的式子变形(根据秦九韶算法.

得到这样的式子

$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.

如果不懂的话还是用笔试一下.

这样我们模拟的就是这个从里向外求解的过程.

所以我们求出来的一定会是我们的答案.

------------------代码-------------------

#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);
}