luogu P1412 经营与开发 |dp
2024-09-01 11:49:27
题目描述
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位小数),表示最大的收入。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
#define db double
int type[N],a[N];
db dp[N];
signed main(){
int n,k,c,w; cin>>n>>k>>c>>w;
for(int i=1;i<=n;i++) scanf("%d%d",&type[i],&a[i]);
for(int i=n;i>=1;i--){
if(type[i]==1)
dp[i]=max(dp[i+1],(1-0.01*k)*dp[i+1]+a[i]);
else dp[i]=max(dp[i+1],(1+0.01*c)*dp[i+1]-a[i]);
}
printf("%.2lf\n",dp[1]*w);
}
最新文章
- 关于#define for if(false);else for
- Oracle数据库的创建以及远程连接(PL/SQL Developer远程连接数据库)
- javascript学习 真正理解DOM脚本编程技术背后的思路和原则
- PHP中逻辑运算符and/or与||/&;&;的一个坑
- Android 反编译
- A web crawler design for data mining
- MDX 占比同比环比
- Eclipse SVN插件账号、密码修改
- ISO 学习笔记 2015-03-15
- FingerChaser(3) 解题报告目录
- 使用Keil软件编写汇编源程序应注意事项
- Windows Server 2008 如何在IIS中添加MIME类型
- 在nuget上发布自己的程序集教程
- css基础系列
- hadoop部署
- 小米平板2 win10 MIUI互刷教程
- Django 日志
- SpringMVC 请求响应流程
- 前端学习 -- Css -- 否定伪类
- C语言版——点亮LED灯,深入到栈