经营与开发 (exploit. cpp/c/pas)

题目描述

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 \leq 100\)

另有 20% 的数据 \(n \leq 1000, k = 100\)

对于 100% 的数据 \(n \leq 100000, 0 \leq k, c, w, a[i], b[i] \leq 100\); 保证答案不超过\(10^9\)

Explanation

直接上官方题解:

“依次飞过 n 个星球”, 第一反应就是动态规划, 然后验证下无后效性即可. 这题关键点为状态的设计.

Method 1

F [i] [x] 表示到达第 i 个星球, 且钻头能力值为 x 的最大收入值.

x 因为是实数, 所以要取一定的精度. 对于数值范围都在 100 的本题, n 在 10 左右的时候毫无压力.

时空复杂度:\(O(n \cdot x)\) x 为精度范围.

期望得分: 10-30;

Method 2

F [i] [x] [y] 表示到达第 i 个星球, 且之前开采过 x 次, 维修过 y 次.

因为本题开采和维修对钻头的影响都是定值. 所以钻头能力就是 \(w \cdot k^x \cdot c^y\)

时空复杂度:\(O(n^3)\)

期望得分: 30

Method 3

对于 20%\(k=100\) 的数据, 钻头开采一次就永久损坏了. 所以只需记录维修过几次即可.

时空复杂度:\(O(n^2)\)

期望得分: 20 (配合 Method 2 为 50)

Method 4

与 Method 2 一样的状态设计. 但是 x, y 的范围不需要与 n 相同. 因为在随机情况下, 开采和维 修的次数寥寥无几 (结合次幂考虑).

时空复杂度:\(O(n \cdot x \cdot y)\) x, y 为选手选择的范围

期望得分: 30-80

Method 5

与 Method 2 一样的状态设计, 但是使用 BFS 来进行 DP 过程, 这样就不会遍历到没有被访问到 的状态, 同时选手可以自己加上一些简单的贪心判断来减少状态数量.

时空复杂度: O (玄学)

期望得分: 70-100

Method 6

与前 5 种做法截然不同. 前 5 种做法的最大瓶颈就是 “当前钻头能力”, 下面我们尝试不存储 “当前钻头能力”.

F [i] 表示前 i 个星球的最优收入. 很明显这是不行的, 因为当前钻头能力会切实影响到后面 的过程, 不严谨的说, 当前钻头能力有 “后效性”.

但是这个当前钻头能力对后程的影响无非就是乘上一个数值. (就好像初始钻头能力为 w, 实际上你可以按 1 来做, 最后再把 ans 乘上 w).

正难则反, F [i] 表示第 i--n 个星球的最优收入, 且假设从第 i 个星球开始时钻头能力为 1. 换句话说, 这样的状态设计, 规定了一个参考系.

转移过程就变得简单: 如果在第 i 个星球开采, 那么第 i+1--n 个星球的初始钻头能力就是 \(1 \times (1 - 0.01k)\). 换句话说, 就是 \(F[i+1] \times (1 - 0.01k)\).

所以 \(F[i] = max\{F[i + 1], F[i + 1] \cdot (1 - 0.01k) + a[i]\}\)

对于维护型星球, 大同小异. 就系数和代价的正负而已.

观察方程,\(F[i] = max\{F[i + 1], F[i + 1] \cdot (1 - 0.01k) + a[i]\}\)

实际上就是取下 i+1--n 的最值而已, 所以这题实际上就成了贪心.

Source Code

因为这道题看到部分分就当场懵了, 所以就没有好好做. 这里写的是标程.

#include<cstdio>
#include<algorithm>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;

const int maxn=100010;
int n,w,t[maxn],a[maxn];
double k,c,ans;
int main()
{
    freopen("exploit.in","r",stdin);
    freopen("exploit.out","w",stdout);
    scanf("%d%lf%lf%d",&n,&k,&c,&w);
    k=1-0.01*k;c=1+0.01*c;
    rep(i,n) scanf("%d%d",&t[i],&a[i]);

    for(int i=n;i;i--)
        if (t[i]==1)
            ans=max(ans,ans*k+a[i]);
        else
            ans=max(ans,ans*c-a[i]);
    printf("%.2lf\n",ans*w);
}