经营与开发 @upc_exam_5500
PROBLEM
题目描述
4X概念体系，是指在PC战略游戏中一种相当普及和成熟的系统概念，得名自4个同样以“EX”为开头的英语单词。
eXplore（探索）
eXpand（拓张与发展）
eXploit（经营与开发）
eXterminate（征服）
——维基百科
今次我们着重考虑exploit部分，并将其模型简化：
你驾驶着一台带有钻头（初始能力值w）的飞船，按既定路线依次飞过n个星球。
星球笼统的分为2类：资源型和维修型。（p为钻头当前能力值）
1.资源型：含矿物质量a[i]，若选择开采，则得到a[i]p的金钱，之后钻头损耗k%，即p=p(1-0.01k)
2.维修型：维护费用b[i]，若选择维修，则支付b[i]p的金钱，之后钻头修复c%，即p=p(1+0.01c)
注：维修后钻头的能力值可以超过初始值（你可以认为是翻修+升级）
请作为舰长的你仔细抉择以最大化收入。
输入
第一行4个整数n,k,c,w。
以下n行，每行2个整数type,x。
type为1则代表其为资源型星球，x为其矿物质含量a[i]；
type为2则代表其为维修型星球，x为其维护费用b[i]；
输出
一个实数（保留2位小数），表示最大的收入。
样例输入
5 50 50 10
1 10
1 20
2 10
2 20
1 30
样例输出
375.00
提示
对于30%的数据 n<=100
另有20%的数据 n<=1000；k=100
对于100%的数据 n<=100000; 0<=k,c,w,a[i],b[i]<=100；保证答案不超过10^9
SOLUTION
因为每次决策具有后效性，考虑倒着贪心。
ans表示从当前星球出发到最后一个星球还能取得的最大收益。
每个决策实际上就是使以后的收入乘以一个系数（1-k%或1+c%）再加上或减去一个当前决策的收益（a[i]或b[i]）
数学原理：秦九韶算法。
CODE
#define IN_PC() freopen("C:\\Users\\hz\\Desktop\\in.txt","r",stdin)
#define IN_LB() freopen("C:\\Users\\acm2018\\Desktop\\in.txt","r",stdin)
#define OUT_PC() freopen("C:\\Users\\hz\\Desktop\\out.txt","w",stdout)
#define OUT_LB() freopen("C:\\Users\\acm2018\\Desktop\\out.txt","w",stdout)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;
int a[MAXN],b[MAXN];
int main() {
// IN_PC();
int n,k,c,w;
scanf("%d%d%d%d",&n,&k,&c,&w);
for(int i=0;i<n;i++){
scanf("%d%d",a+i,b+i);
}
double ans = 0;
double K = 1-0.01*k,C = 1+0.01*c;
for(int i=n-1;i>=0;i--){
if(a[i]==1){
ans = max(ans,ans*K+b[i]);
}else{
ans = max(ans,ans*C-b[i]);
}
}
printf("%0.2f\n",ans*w);
return 0;
}