2.17NOIP模拟赛(by hzwer) T1 小奇挖矿

【题目背景】

　　小奇要开采一些矿物,它驾驶着一台带有钻头(初始能力值 w)的飞船,按既定
　　路线依次飞过喵星系的 n 个星球。

【问题描述】

　　星球分为 2 类:资源型和维修型。

　　1. 资源型:含矿物质量 a[i],若选择开采,则得到 a[i]*p 的金钱,之后钻头
　　损耗 k%,即 p=p*(1-0.01k)

　　2. 维修型:维护费用 b[i],若选择维修,则支付 b[i]*p 的金钱,之后钻头修
　　复 c%,即 p=p*(1+0.01c)(p 为钻头当前能力值)

　　注:维修后钻头的能力值可以超过初始值
　　请你帮它决策最大化这个收入

【输入格式】

　　第一行 4 个整数 n,k,c,w。
　　以下 n 行,每行 2 个整数 type,x。
　　type 为 1 则代表其为资源型星球,x 为其矿物质含量 a[i];
　　type 为 2 则代表其为维修型星球,x 为其维护费用 b[i];

【输出格式】

　　输出一行一个实数(保留两位小数),表示要求的结果。

【样例输入】

　　5 50 50 10
　　1 10
　　1 20
　　2 10
　　2 20
　　130

【样例输出】

　　375.00

【数据范围】

　　对于 30%的数据 n<=100
　　对于 50%的数据 n<=1000,k=100
　　对于 100%的数据 n<=100000,0<=k,c,w,a[i],b[i]<=100
　　保证答案不超过 10^9

【解析】

　　这道题从题面就可以看出是一道动态规划的题，但有一点显然的是：前面的决策会影响后面的结果。为了消去前面的影响，我们可以从后边开始动态规划。

　　设f[i]表示在第i个星球的最大收入。若当前点为资源型星球，那么如果开采就可以获得当前星球的收入，而由于耐久度会减少，前面所得到的收入要整体下降%k所以状态转移方程为f[i]=max(f[i-1],a[i]+f[i-1]*(1-0.01*k))。若当前点为维修型星球，那么同理可得：减少a[i]并让前面的收入增加%c，状态转移方程为f[i]=max(f[i-1],f[i-1]*(1+0.01*c)-a[i])。为了在状态转移时更加方便，我们可以将原来耐久度为w的钻机分解成w个耐久为一的钻机，最后给答案乘w即可。

　　综上所述，状态转移方程为：

　　f[i]=max(f[i-1],a[i]+f[i-1]*(1-k%)) (t[i]=1)

　　f[i]=max(f[i-1],f[i-1]*(1+c%)-a[i]) (t[i]=2)

【代码】

 #include <bits/stdc++.h>

 #define N 100002

 using namespace std;

 int n,d[N],a[N],i;

 double f[N],k,c,w;

 int main()

 {

     freopen("explo.in","r",stdin);

     freopen("explo.out","w",stdout);

     cin>>n>>k>>c>>w;

     for(i=;i<=n;i++) cin>>d[i]>>a[i];

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

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

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

     }

     f[]=f[]*w;

     cout<<setprecision()<<fixed<<f[]<<endl;

     return ;

 }

P.S. 转载自LSlzf

巴特西