【洛谷P1412】经营与开发

题目

题目链接：https://www.luogu.com.cn/problem/P1412
你驾驶着一台带有钻头（初始能力值 (w)）的飞船，按既定路线依次飞过 (n) 个星球。
星球笼统的分为 (2) 类：资源型和维修型。（ (p) 为钻头当前能力值）

1. 资源型：含矿物质量 (a[i])，若选择开采，则得到 (a[i] imes p) 的金钱，之后钻头损耗 (k\%)，即 (p=p imes (1-0.01k))。
2. 维修型：维护费用 (b[i])，若选择维修，则支付 (b[i] imes p) 的金钱，之后钻头修复 (c\%)，即 (p=p imes (1+0.01c))。

注：维修后钻头的能力值可以超过初始值（你可以认为是翻修+升级）
金钱可以透支。
请作为舰长的你仔细抉择以最大化收入。

思路

假设到了第 (i) 个星球时，钻头的能力值为 (p)，我们依然可以设其为 (1)，然后后面所有运算乘上 (p) 即可。
所以我们倒着 dp，设 (f[i]) 表示假设到第 (i) 个星球的时候钻头能力值为 (1)，接下来经过 (isim n) 的星球最大收益。
假设下一个星球是资源型的，显然

[f[i]=max(f[i+1],f[i+1] imes (1-k\%)+a[i]) ]

维修性同理。答案即为 (f[1])。
时间复杂度 (O(n))。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=100010;
int n,k,c,w,opt[N],a[N];
double f[N];

int main()
{
	scanf("%d%d%d%d",&n,&k,&c,&w);
	for (int i=1;i<=n;i++)
		scanf("%d%d",&opt[i],&a[i]);
	for (int i=n;i>=1;i--)
		if (opt[i]==1) f[i]=max(f[i+1],f[i+1]*(1-k/100.0)+a[i]);
			else f[i]=max(f[i+1],f[i+1]*(1+c/100.0)-a[i]);
	printf("%.2lf",w*f[1]);
	return 0;
}