【7.10校内test】T3经营与开发

它……又是个DP

我……我讨厌DP!?

然后又是读入，显然用快读啊：（数据范围还是很大的）（习惯）

然后我们发现，不论是损耗值维修值，还是采矿所得，维修花费，都带着个p，因此我们可以把p提出来？

dp[i]表示第i个星球~第n个星球的最大赚取费用；

那么我们的解就是dp[1]；

考虑一下：

假设第i个是资源型，在之前已经求出dp[i+1]（代表从i+1开始选，1～i一概略过）的最大金钱数，那么dp[i]=max(dp[i+1]/*这个不选*/, a[i]+dp[i+1]*(1-0.01*k)/*第i个选了，加上金钱，当前钻头能力系数变为原来的(1-0.01*k)，那么后面的得到的最大金钱数也变为原来的(1-0.01*k)*/)

那么如果第i个是资源型也同理，如果我们选了它，那么对后面dp[i+1]，会使它的钻头能力变为原来的(1+0.01*c)倍，当然记得减去a[i]（把p已经提出来了qwq）

因此核心代码：

if(t[i]==) dp[i]=max(dp[i+],dp[i+]*(-0.01*k)+a[i]);

        else dp[i]=max(dp[i+],dp[i+]*(+0.01*c)-a[i]);

最后不要忘记再将w乘回来（因为实际上p的改变都乘在dp数组中了，所以只需要乘原始值）

#include<bits/stdc++.h>

using namespace std;

inline int read(){

    int ans=;

    char last=' ',ch=getchar();

    while(ch>''||ch<'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

int n;

double k,c,w;

int x[],type[];

double f[];

int main(){

    n=read();

    scanf("%lf%lf%lf",&k,&c,&w);

    for(int i=;i<=n;i++){

        type[i]=read();

        x[i]=read();

    }

    for(int i=n;i>=;i--){

        if(type[i]==) f[i]=max(f[i+],f[i+]*(-0.01*k)+x[i]);

        else f[i]=max(f[i+],f[i+]*(+0.01*c)-x[i]);

    }

    printf("%.2lf",f[]*w);

    return ;

}

忍不住说某些s*jl

end-

巴特西

【7.10校内test】T3经营与开发

最新文章

热门文章