模拟赛 Problem 3 经营与开发(exploit.cpp/c/pas)
Problem 3 经营与开发(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<=100
另有20%的数据 n<=1000;k=100
对于100%的数据 n<=100000; 0<=k,c,w,a[i],b[i]<=100;保证答案不超过10^9
思路:dp。可以发现,当前的决策只对后面的开采有影响,且剩余耐久度与之后的开采收益成正比,如果倒着考虑这个问题,得出i-n的星球1点耐久度所能获得的最大收益,从后往前dp,得出最大值最后乘w就是答案。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100001
using namespace std;
int n,w;
int 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=-0.01*k;c=+0.01*c;
for(int i=;i<=n;i++)
scanf("%d%d",&t[i],&a[i]);
for(int i=n;i;i--)
if(t[i]==)
ans=max(ans,ans*k+a[i]);
else
ans=max(ans,ans*c-a[i]);
printf("%.2lf\n",ans*w);
}
最新文章
- Notepad++源码编译及其分析
- 大型web系统数据缓存设计
- C#.NET 大型通用信息化系统集成快速开发平台 4.1 版本 - 忘记密码功能改进、手机短信、电子邮件
- 在Android中使用Java 8的lambda表达式
- poj 1659 Frogs&#39; Neighborhood Havel-Hakimi定理 可简单图定理
- Git 基础 - Git Aliases
- linux中cat more less head tail 命令区别
- android Gallery滑动不流畅的解决
- hdu4758 Walk Through Squares 自动机+DP
- vi/vim多行注释和取消注释
- PM意识升级2.0
- js动态修改Easyui元素不生效,EasyUI动态渲染解析解决方案
- 深入学习使用ocr算法识别图片中文字的方法
- 关于es6中的yield
- CentOs安装和使用
- python socket 老生常谈
- 黑马-Spring与数据库
- Andrew Ng-ML-第十四章-无监督学习
- Vue源码解析之数组变异
- 开源代码ViewPageIndicator的使用
热门文章
- [CREC2007/CQOI2014]robotic sort
- SQL server存储过程及触发器基础
- get、post、put、delete、head请求方式
- Pyhton TestCase运行闪退与失败,原因不详。。。
- (转)解决office软件无法卸载也无法安装的顽固问题
- 【sqli-labs】 对于less34 less36的宽字节注入的一点深入
- CAD绘制一个图象标记对象(com接口VB语言)
- docker常用命令理解
- &#39;dict&#39; object is not callable
- Java基本数据类型、包装类与String类之间的转换