[动态规划]小奇挖矿

暂无传送门

----------

####题目描述:
小奇要开采一些矿物，它驾驶着一台带有钻头（初始能力值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.01k)$
(p为钻头当前能力值） 
注：维修后钻头的能力值可以超过初始值 
请你帮它决策最大化这个收入

####输入格式

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

####输出格式

输出一行一个实数（保留两位小数），表示要求的结果。

----------
###题解:
不难发现,如果我们从前往后dp,会有后效性,因为进行操作会对后面操作的价值产生影响.
那我们不妨从后往前dp,f[i]表示在第 $i$ 号星球进行相应的操作,且前面没有进行任何操作的最大收入.如果我们从后往前dp的话,就很好转移了.因为这一次操作会对p乘上$(1+0.01c)$或$(1-0.01k)$,那么只需要找出它后面最大的f值,并算上这次操作对它的影响即可.
方程:
$f[i]=\max_{j=i+1}^nf[j]*(1-0.01k)+v[i]$(采矿星球)
$f[i]=\max_{j=i+1}^nf[j]*(1+0.01c)-v[i]$(修复星球)

----------
贴上代码:
```
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define maxn 100005
using namespace std;
struct node{int ty;double p;}a[maxn];
double f[maxn],k,c,w,mmax=0;
int n;
int main()
{
	scanf("%d%lf%lf%lf",&n,&k,&c,&w);
	for(int i=1;i<=n;i++) scanf("%d%lf",&a[i].ty,&a[i].p);
	k/=100.0,c/=100.0;
	for(int i=n;i>=1;i--)
	{
		if(a[i].ty==1) f[i]=mmax*(1-k)+a[i].p;
		else f[i]=mmax*(1+c)-a[i].p;
		mmax=max(mmax,f[i]);
	}
	printf("%.2lf",mmax*w);
	return 0;
}
```

PhantasmDragon 's Blog