[题解][洛谷P1412] 经营与开发

题目描述

给定n，k，c，w，然后输入n组数据，数据分为两种：

• 1 ai：可以选择获得aiw的价值，但w会变成w（1-0.01*k)
• 2 bi：可以选择损失biw的价值，但w会变成w（1+0.01*c）
  求可获得的最大价值是多少。

题解
看到这个题，我的第一思路是求后缀和，然后让新得到的系数乘后缀和判断是否进行操作。
但问题在于，对于后缀和，我们并不会一定每一个数据进行操作，因此不是正解。
反过来想一想，如果我们从n开始倒着求，还是用类似的思路，可以保证系数所乘的数是目前的最优解，可以解决这个问题。
设初始系数为1，那么状态转移方程就是f[i]=max(f[i+1],f[i+1]x(1+0.01c)-a[i]）及 f[i]=max(f[i+1],f[i+1]x(1-0.01k)+a[i]）。

代码

#include<bits/stdc++.h>
using  namespace std;
const int N=1e6+7;
double f[N];
struct star{
	int t;
	double x;
}a[N];
int main(){
	int n;
	double k,c,w;
	cin>>n>>k>>c>>w;
	for(int i=1;i<=n;i++)cin>>a[i].t>>a[i].x;
	for(int i=n;i>=1;i--){
		if(a[i].t==1)f[i]=max(f[i+1],a[i].x+f[i+1]*(1-0.01*k));
		else f[i]=max(f[i+1],-a[i].x+f[i+1]*(1+0.01*c));
	}
	printf("%.2lf",f[1]*w);
}