自动搬运

查看原文

来自洛谷，原作者为

	poorpool **

搬运于2025-08-24 21:24:48，当前版本为作者最后更新于2017-10-20 16:10:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻也能写出来的AC代码！其实刚拿到这道题是我是不会做的……因为我惯性思维了，老是想着从1推到n，但是这样是有后效性的。

不过，正难则反，既然从1到n有后效性了，那么我们想着从n推到1。可以看出来一个星球选择与否对后面的影响是成比例的，也就是说只是系数的差别。

举个例子，第i个是资源型，我们可以搞出dp[i+1]（代表从i+1开始选，1～i一概略过）的最大金钱数，钦定第i个开始选的系数为1，那么dp[i]=max(dp[i+1]/*这个不选*/, a[i]+dp[i+1]*(1-0.01*k)/*第i个选了，加上金钱，当前钻头能力系数变为原来的(1-0.01*k)，那么后面的得到的最大金钱数也变为原来的(1-0.01*k)*/)

代码量很少但是思维还是很有难度的qwq

#include <iostream>
#include <cstdio>
using namespace std;
int n, f[100005], a[100005];
double c, k, w, dp[100005];
int main(){
    cin>>n>>k>>c>>w;
    for(int i=1; i<=n; i++)
        scanf("%d %d", &f[i], &a[i]);
    for(int i=n; i>=1; i--){
        if(f[i]==1)    dp[i] = max(dp[i+1], a[i]+dp[i+1]*(1-0.01*k));
        else        dp[i] = max(dp[i+1], -a[i]+dp[i+1]*(1+0.01*c));
    }
    printf("%.2lf", dp[1]*w);
    return 0;
}