题解 P1412 【经营与开发】

# [顾](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); } ```