动态规划P4269经营与开发

我就是我 2021-11-11 01:56 226阅读 0赞

###### **问题如下** ######

###### 问题描述 ######

你驾驶着一台带有钻头（初始能力值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

**分析**

先考虑如下

1.**状态**：f\[i\]\[x\]\[y\]:已到i号星球，1-i之中，修了x次，采y次的最大收益

**方程**：

f\[i\]\[x\]\[y\]=max\{(1),(2),(3)\}

(1)f\[i-1\]\[x\]\[y\]

(2)i为资源，f\[i-1\]\[x\]\[y-1\]+w\*(1+0.01c)^x\*(1-0.01k)^(y-1)\*a\[i\]

(3)i为修理，f\[i-1\]\[x-1\]\[y\]-w\*(1+0.01c)^(x-1)\*(1-0.01k)^y\*b\[i\]

时间复杂读度（o(n^3)）

显然会**超时**

为排除后效性，我们考虑由后往前

2.**状态**：f\[i\]；从i到n号星球的最大收入

**方程**：

f\[i\]=max\{(1),(2),(3)\}

(1)f\[i+1\]

(2)i为修理;f\[i\]=f\[i+1\]\*(1+0.01c)-b\[i\]

(3)i为资源f\[i\]=f\[i+1\]\*(1-0.01k)+a\[i\]

时间复杂读度（o(n)）

可过！！！！

下面是蒟蒻丑陋的代码

//
    #include<stdio.h>
    #include<bits/stdc++.h>
    using namespace std;
    double f[100005];
    int a[100005],m[100005];
    int n,w,q;
    double c,k;
    int main()
    {
        cin>>n>>k>>c>>w;
        for(int i=1; i<=n; i++)
        {
            cin>>m[i]>>a[i];
        }
        for(int i=n;i>=1;i--)
        {
            if(m[i]==2)
            f[i]=max(f[i+1],(f[i+1]*(1+0.01*c)-a[i]));
            if(m[i]==1)
            f[i]=max(f[i+1],(f[i+1]*(1-0.01*k)+a[i]));
        }
        printf("%0.2lf",f[1]*w);
    }

另，f\[i\]可改为一个变量ans，这样可以少一个数组。。。。

转载于:https://www.cnblogs.com/CXYscxy/p/11028041.html