维护一段连续区间的极值并且快速取出 用双端队列维护单调的序列
下面来到例题目
最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。
通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股APi，第i天的股票卖出价为每股BPi（数据保证对于每个i，都有APi>=BPi），但是每天不能无限制地交易，于是股票交易所规定第i天的一次买入至多只能购买ASi股，一次卖出至多只能卖出BSi股。
另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔W天，也就是说如果在第i天发生了交易，那么从第i+1天到第i+W天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过MaxP。
在第1天之前，lxhgww手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，T天以后，lxhgww想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？
解：
背包问题
定义f[i][j]表示i天持有j股票 所获得的最大收益 第i天不一定要买
所以方程转移为
(f[i][j]=max(f[i-w-1][k]+(k-j)*b,f[i-w-1][k]-(j-k)*a,f[i-1][j]);)
然后提取常数
注意到k的范围为$ [j,j+b[i]] 和[j-a[i],j];$
满足一段区间求极大极小值
所以就可以利用单调队列进行优化
为甚们是i-w-1 ? 而不是前面的数
因为我们定义的时候i-w-1 并不是一定要买 所以是前面的最优状态
至于初始值怎么赋？
除了f[0][0] 的状态都赋值为-inf
其余的每次取到能买的上限 具体看代码
code:
//
#include<bits/stdc++.h>
using namespace std;
#define maxnn 3000
#define ll long long
ll T,P,w;
ll f[maxnn][maxnn];
ll A1[maxnn],A2[maxnn],B1[maxnn],B2[maxnn];
deque<int > Q;
int main()
{
cin>>T>>P>>w;
for(int i=1;i<=T;i++){
cin>>A1[i]>>B1[i]>>A2[i]>>B2[i];
}
for(int i=0; i<=T; i++)for(int j=0; j<=P; j++)f[i][j]=-2333333;
f[0][0]=0;
for(int i=1; i<=T; i++) {
Q.clear();
for(int j=0; j<=A2[i]; j++)f[i][j]=-j*A1[i];
for(int j=0; j<=P; j++)f[i][j]=max(f[i][j],f[i-1][j]);
if(i-w-1<0)continue;
Q.clear();
Q.push_back(0);
int index=0;
for(ll j=0;j<=P;j++)
{
while(Q.size()&&Q.front()<j)
{
Q.pop_front();
}
while(index<=min(P,B2[i]+j))
{
while(Q.size()&&(f[i-w-1][Q.back()]+B1[i]*Q.back())<=(f[i-w-1][index]+B1[i]*index))
{
Q.pop_back();
}
Q.push_back(index);
index++;
}
f[i][j]=max(f[i][j],f[i-w-1][Q.front()]+B1[i]*(Q.front())-j*B1[i]);
}
index=0;
Q.clear();
Q.push_back(index);
for(ll j=0;j<=P;j++)
{
while(Q.size()&&Q.front()<j-A2[i])
{
Q.pop_front();
}
while(index<=min(P,j))
{
while(Q.size()&&(f[i-w-1][Q.back()]+A1[i]*Q.back())<=(f[i-w-1][index]+A1[i]*index))
{
Q.pop_back();
}
Q.push_back(index);
index++;
}
f[i][j]=max(f[i][j],f[i-w-1][Q.front()]+A1[i]*(Q.front())-j*A1[i]);
}
}
ll ans=-111110;
for(int i=0;i<=P;i++)
{
ans=max(ans,f[T][i]);
}
cout<<ans;
}