经营与开发 @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
",ans*w);
    return 0;
}