最近 \(lxhgww\) 又迷上了投资股票,通过一段时间的观察和学习,他总结出了股票行情的一些规律。

通过一段时间的观察,\(lxhgww\) 预测到了未来 \(T\) 天内某只股票的走势,第 \(i\) 天的股票买入价为每股 \(AP_i\),第 \(i\) 天的股票卖出价为每股 \(BP_i\)(数据保证对于每个 \(i\),都有 \(AP_i \geq BP_i\)),但是每天不能无限制地交易,于是股票交易所规定第 ii 天的一次买入至多只能购买 \(AS_i\) 股,一次卖出至多只能卖出 \(BS_i\) 股。

另外,股票交易所还制定了两个规定。为了避免大家疯狂交易,股票交易所规定在两次交易(某一天的买入或者卖出均算是一次交易)之间,至少要间隔 \(W\) 天,也就是说如果在第 \(i\) 天发生了交易,那么从第 \(i+1\) 天到第 \(i+W\)天,均不能发生交易。同时,为了避免垄断,股票交易所还规定在任何时间,一个人的手里的股票数不能超过 \(MaxP\)。

在第 11 天之前,\(lxhgww\) 手里有一大笔钱(可以认为钱的数目无限),但是没有任何股票,当然,\(T\) 天以后,\(lxhgww\) 想要赚到最多的钱,聪明的程序员们,你们能帮助他吗?

输入输出格式

输入数据第一行包括 33 个整数,分别是 \(T\),\(\text{MaxP}\),\(W\)。

接下来 \(T\) 行,第 \(i\) 行代表第 \(i-1\)天的股票走势,每行 \(4\) 个整数,分别表示 \(AP_i,\ BP_i,\ AS_i,\ BS_i\)

输出数据为一行,包括 \(1\) 个数字,表示 \(lxhgww\) 能赚到的最多的钱数。

5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1
3

说明

对于 \(30\%\) 的数据,\(0\leq W<T\leq 50,1\leq\text{MaxP}\leq50\)

对于 \(50\%\) 的数据,\(0\leq W<T\leq 2000,1\leq\text{MaxP}\leq50\)

对于 \(100\%\) 的数据,\(0\leq W<T\leq 2000,1\leq\text{MaxP}\leq2000\)

对于所有的数据,\(1\leq BP_i\leq AP_i\leq 1000,1\leq AS_i,BS_i\leq\text{MaxP}\)


这题真的难,写了我两个小时。(也可以等效于我是真的菜)

不打算讨论题目的解题思路,就是单纯的讲一下这三天写单调队列的感受吧。

  • 刚看到一个题目不用刻意去想是不是单调队列。
  • 能用单调队列写的首先通常有一个复杂度爆炸的暴力。
  • 其形式通常为一个包含多变量的明确的状态方程,有的变量可能会非常大。
  • 单队特称明显,暴力转单调队列是自然而然的事情。
  • 一开始跳过暴力直接写正解,很容易导致正确性出现问题。(除非题目很简单)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 2010
#define INF 0x7fffffff
using namespace std; int h1,t1,h2,t2;
int n,m,w,ans,AP[MAXN],BP[MAXN];
int AS[MAXN],BS[MAXN],f[MAXN][MAXN]; struct node{
int nod,val;
}q1[MAXN],q2[MAXN]; int main(){
cin>>n>>m>>w;
for(register int i=1;i<=n;++i){
cin>>AP[i]>>BP[i]>>AS[i]>>BS[i];
}
memset(f,-0x3f,sizeof(f));f[0][0]=0;
for(register int i=1;i<=n;++i){//枚举当前哪一天
for(register int j=0;j<=m;++j){
if(j<=AS[i]){//如果一次购买可以达到j股
f[i][j]=max(f[i][j],f[0][0]-AP[i]*j);
}
f[i][j]=max(f[i][j],f[i-1][j]);//不作购买
}
h1=1,t1=0,h2=1,t2=0;
for(register int j=1;j<=m;++j){
if(i-w-1>0){
node ins;ins.nod=j-1;
ins.val=f[i-w-1][j-1]+AP[i]*(j-1);
while(h1<=t1 && q1[t1].val<=ins.val)t1--;
q1[++t1]=ins;
while(h1<=t1 && q1[h1].nod<j-min(j,AS[i]))h1++;
f[i][j]=max(f[i][j],q1[h1].val-AP[i]*j);
}
}
for(register int j=m-1;j>=0;--j){
if(i-w-1>0){
node ins;ins.nod=j+1;
ins.val=f[i-w-1][j+1]+BP[i]*(j+1);
while(h2<=t2 && q2[t2].val<=ins.val)t2--;
q2[++t2]=ins;
while(h2<=t2 && q2[h2].nod>j+min(m-j,BS[i]))h2++;
f[i][j]=max(f[i][j],q2[h2].val-BP[i]*j);
}
}
}
for(register int i=1;i<=n;++i){
for(register int j=0;j<=m;++j){
ans=max(ans,f[i][j]);
}
}
cout<<ans<<endl;
}

最新文章

  1. webpack构建vue项目(配置篇)
  2. react+redux教程(一)connect、applyMiddleware、thunk、webpackHotMiddleware
  3. ORA-12560: TNS: 协议适配器错误 ORA-12154: TNS: 无法解析指定的连接标识符
  4. Gvim常用命令
  5. [BZOJ2730][HNOI2012]矿场搭建(求割点)
  6. JS阻止链接跳转代码
  7. CSS中!important的优先级
  8. CGContextAddArcToPoint和CGContextAddArc
  9. LeetCode49 Group Anagrams
  10. BootStrap--模态框中 上传图片
  11. Jenkins详细安装与构建部署使用教程(转)
  12. Python开发环境Wing IDE 5.0测试第八版发布
  13. centos7下安装mysql5.7.17
  14. 02_HTML5+CSS详解第一天
  15. python random使用方法
  16. SPARK安装三:SPARK集群部署
  17. 【转】R语言 RStudio快捷键
  18. tp5增删改查
  19. using关键字在C#中的3种用法
  20. Linux文件的时间

热门文章

  1. Linux内核分析第三周学习总结
  2. Linux内核 实践二
  3. 同步手绘板——json
  4. 在Eclipse中使用JUnit4进行单元测试(图文教程一)
  5. I/O(输入/输出)
  6. nodejs框架对比
  7. java数值运算后精度丢失问题
  8. Spring源码阅读学习一
  9. JavaScript(ECMAScript) with 语句
  10. js中如何优雅的写if判断