洛谷 P2569 [SCOI2010] 股票交易

题目来源于:洛谷

题目本质:动态规划,单调队列

解题思路:

方程f[i][j]表示第 i 天结束后,手里剩下 j 股的最大利润,则不买不卖:f[i][j]=f[i-1][j]。

买入:f[i][j]=max{f[i-w-1][k]+k*ap[i]}-ap[i]*j

卖出:f[i][j]=max{f[i-w-1][k]+k*bp[i]}-bp[i]*j

完整代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int t,maxp,w;
int ap[N],bp[N],as[N],bs[N];
int f[N][N];
int q[10000],qhead=1,qtail=0;
int main(){scanf("%d%d%d",&t,&maxp,&w);for(int i=1;i<=t;i++){scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);}memset(f,-0x7f,sizeof(f));for(int i=0;i<=t;i++){f[i][0]=0;}for(int i=1;i<=t;i++){for(int j=0;j<=as[i];j++){f[i][j]=-ap[i]*j;}for(int j=maxp;j>=0;j--){f[i][j]=max(f[i][j],f[i-1][j]);}if(i-w-1>=0){qhead=1;qtail=0;for(int j=0;j<=maxp;j++){while(qhead<=qtail&&q[qhead]<j-as[i]){qhead++;}while(qhead<=qtail&&f[i-w-1][j]+ap[i]*j>=f[i-w-1][q[qtail]]+ap[i]*q[qtail]){qtail--;}q[++qtail]=j;if(qhead<=qtail){f[i][j]=max(f[i][j],f[i-w-1][q[qhead]]-ap[i]*(j-q[qhead])); }} qhead=1;qtail=0;for(int j=maxp;j>=0;j--){while(qhead<=qtail&&q[qhead]>j+bs[i]){qhead++;}while(qhead<=qtail&&f[i-w-1][j]+bp[i]*j>=f[i-w-1][q[qtail]]+bp[i]*q[qtail]){qtail--;}q[++qtail]=j;if(qhead<=qtail){f[i][j]=max(f[i][j],f[i-w-1][q[qhead]]+bp[i]*(q[qhead]-j));}} } }int ans=0;for(int i=0;i<=maxp;i++){ans=max(f[t][i],ans);}printf("%d",ans);return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/408680.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue3+ts+Go使用百度地图路书实现历史轨迹回放、轨迹回放进度、聚合点、自定义弹框和实时监控视频、多路视频轮巡播放

前言 分享一个刚做完项目集成技术&#xff0c;一个车辆行驶轨迹监控、行车视频监控、对特种车辆安全监管平台&#xff0c;今年政府单位有很多监管平台项目&#xff0c;例如&#xff1a;渣土车监控、租出车监管、危害气体运输车监管等平台&#xff0c;这些平台都有车辆行驶轨迹…

uniapp实现区域滚动、下拉刷新、上滑滚动加载更多

背景&#xff1a; 在uniapp框架中&#xff0c;有两种实现办法。第1种&#xff0c;是首先在page.json中配置页面&#xff0c;然后使用页面的生命周期函数&#xff1b;第2种&#xff0c;使用<scroll-view>组件&#xff0c;然后配置组件的相关参数&#xff0c;包括但不限于&…

Spring(一篇就懂)

Spring框架简介 Spring 是一个开源的Java企业级应用开发框架。 特点&#xff1a; 控制反转&#xff08;IoC&#xff09;&#xff1a;通过依赖注入&#xff08;DI&#xff09;减少组件间的耦合&#xff0c;由Spring容器负责对象的创建和绑定。 面向切面编程&#xff08;AOP&am…

企业高性能web服务器(nginx)

目录 Web服务器基础介绍 正常情况下的单次web服务器访问流程 Apache 经典的 Web服务端 Apache prefork 模型 Apache work模型 Apache event模型 服务端的I/O流程 服务器的I/O 磁盘I/O 网络I/O 网络I/O处理过程 I/O模型 I/O模型相关概念 同步/异步 阻塞/非阻塞 网…

面向对象06:super关键字详解

本节内容视频链接&#xff1a;面向对象10&#xff1a;Super详解_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV12J41137hu?p69&vd_sourceb5775c3a4ea16a5306db9c7c1c1486b5 Java中的‌super关键字是一个特殊的引用&#xff0c;‌用于指代父类对象‌。‌在子…

鸿蒙HarmonyOS实战:IPC与RPC设备内进程通信

基本 IPC&#xff08;Inter-Process Communication&#xff09;与RPC&#xff08;Remote Procedure Call&#xff09;用于实现跨进程通信&#xff0c;不同的是前者使用Binder驱动&#xff0c;用于设备内的跨进程通信&#xff0c;后者使用软总线驱动&#xff0c;用于跨设备跨进…

学习yolo+Java+opencv简单案例(三)

主要内容&#xff1a;车牌检测识别&#xff08;什么颜色的车牌&#xff0c;车牌号&#xff09; 模型作用&#xff1a;车牌检测&#xff0c;车牌识别 文章的最后附上我的源码地址。 学习还可以参考我前两篇博客&#xff1a; 学习yoloJavaopencv简单案例&#xff08;一&#xff0…

Datawhale X 李宏毅苹果书 AI夏令营-深度学习入门班-task2

一开始假设的模型是ybw1&#xff0c;但在可视化预测值和真实值后&#xff0c;发现数据具有规律性&#xff0c;因此换成7天 额&#xff0c;不知道为什么要在这里这样引入sigmoid函数&#xff0c;有点怪怪的&#xff0c;但确实用无限多的分段函数就能拟合很多曲线 所以这里的意…

5步实现猫眼电影爬虫与k-means算法可视化分析

&#x1f34a;作者&#xff1a;计算机毕设匠心工作室 &#x1f34a;简介&#xff1a;毕业后就一直专业从事计算机软件程序开发&#xff0c;至今也有8年工作经验。擅长Java、Python、微信小程序、安卓、大数据、PHP、.NET|C#、Golang等。 擅长&#xff1a;按照需求定制化开发项目…

框架——特殊符号处理,模糊查询

1.特殊符号处理 在 mybatis 中的 xml 文件中&#xff0c;存在一些特殊的符号&#xff0c;比如&#xff1a;<、>、"、&、<>等&#xff0c;正常书写mybatis 会报错&#xff0c;需要对这些符号进行转义。具体转义如下所示&#xff1a; 特殊字符 转义字符 &…

【GNSS射频前端】MA2769初识

MAX2769 芯片概述&#xff1a; MAX2769是一款单芯片多系统GNSS接收器&#xff0c;采用Maxim的低功耗SiGe BiCMOS工艺技术。集成了包括双输入低噪声放大器&#xff08;LNA&#xff09;、混频器、图像拒绝滤波器、可编程增益放大器&#xff08;PGA&#xff09;、压控振荡器&#…

微信小游戏授权问题

微信小程序获取用户相关信息的接口&#xff0c;如wx.getUserCloudStorage&#xff0c;报错&#xff1a;please go to mp to announce your privacy usage。 需要在微信公众平台设置用户隐私保护。

(论文解读)Domain Adaptation via Prompt Learning

摘要 无监督域适应( UDA )旨在将从带有标签的源域数据中学习到的模型适应到未标注的目标域数据集。现有的UDA方法通过对齐源域和目标域特征空间来学习领域不变特征。这种对齐是通过约束实现的&#xff0c;例如统计差异最小化或对抗学习。 然而&#xff0c;这些约束会导致语义…

AudioNotes -将音频内容转 markdown

文章目录 一、关于 AudioNotes效果展示音视频识别和整理与音视频内容对话 二、使用方法1、安装 Ollama2、拉取模型3、部署服务3.1 Docker部署&#xff08;推荐&#xff09;&#x1f433;3.2 本地部署 &#x1f4e6; 一、关于 AudioNotes AudioNotes 能够快速提取音视频的内容&…

【C# 】使用List<实体类>

1. 使用List<实体类> 要在C#中使用List<EntityTemp>并实现查找数据输出&#xff0c;首先需要定义EntityTemp类&#xff0c;并创建一个List<EntityTemp>类型的列表。然后&#xff0c;你可以使用LINQ或其他方法来查找和输出数据。 假设EntityTemp类具有一个…

Kafka快速入门:Kafka驱动JavaApi的使用

生产者和消费者是Kafka的核心概念之一&#xff0c;它们在客户端被创建和使用&#xff0c;并且包含了许多与Kafka性能和机制相关的配置。虽然Kafka提供的命令行工具能够执行许多基本操作&#xff0c;但它无法实现所有可能的性能优化。相比之下&#xff0c;使用Java API可以充分利…

zigbee笔记、十五、组播通信原理

一、zigbee四种通讯 1、单播&#xff08;略&#xff09; 2、广播&#xff08;略&#xff09; 3、组播&#xff1a;在zigbee网络中&#xff0c;模块可以用分组来标记&#xff0c;发送的模块如果发送的组号和网络里面标记接收模块的组号相对应&#xff0c;那么这些模块就可以拿到…

C#/.NET/.NET Core技术前沿周刊 | 第 1 期(2024年8.12-8.18)

前言 C#/.NET/.NET Core技术前沿周刊&#xff0c;你的每周技术指南针&#xff01;记录、追踪C#/.NET/.NET Core领域、生态的每周最新、最实用的技术文章、社区动态、优质项目和学习资源等。让你时刻站在技术前沿&#xff0c;助力技术成长与视野拓宽。 欢迎投稿&#xff0c;推荐…

innodb_buffer_pool_size在线缩小操作

一、背景 测试数据库内存32G&#xff0c;只有MySQL数据库&#xff0c;但是innodb_buffer_pool_size设置了24G&#xff0c;导致经常出现lack of memory问题、lack of swap问题。 因为使用了MySQL5.7.36版本&#xff0c;利用innodb_buffer_pool_size参数值可在线调整的新特性&…

C++函数调用栈从何而来

竹杖芒鞋轻胜马,谁怕?一蓑烟雨任平生~ 个人主页&#xff1a; rainInSunny | 个人专栏&#xff1a; C那些事儿、 Qt那些事儿 文章目录 写在前面原理综述x86架构函数调用栈分析如何获取rbp寄存器的值总结 写在前面 程序员对函数调用栈是再熟悉不过了&#xff0c;无论是使用IDE…