题目描述
最近 WW 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。通过一段时间的观察，\text{lxhgww}lxhgww 预测到了未来 TT 天内某只股票的走势，第 ii 天的股票买入价为每股 AP_i，第 ii 天的股票卖出价为每股 BP_i ，但是每天不能无限制地交易，于是股票交易所规定第 i 天的一次买入至多只能购买 AS_i 股，一次卖出至多只能卖出 BS i股。另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 W 天，也就是说如果在第 i 天发生了交易，那么从第 i+1 天到第 i+W 天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过 MaxP。在第 11 天之前，WW 手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，T 天以后，WW 想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？输入格式
输入数据第一行包括 3 个整数，分别是 T，MaxP，W。接下来 T 行，第 i 行代表第 i?1 天的股票走势，每行 4 个整数，分别表示 AP_i,\ BP_i,\ AS_i,\ BS_iAP i
?
输出格式
输出数据为一行，包括 1 个数字，表示WW能赚到的最多的钱数。
输入输出样例
输入 #1 复制
5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1
输出 #1 复制
3
思路：
设置两次单调队列，一次求卖出的，一次求买入的，这样就能避免卖出买入纵横交错，杂乱无章，毫无头绪
因为 天才能进行一次交易，所以我们只能用 作为前驱
那动态转移方程为：买入：f[i][j]=max(q[k][1]-jxa[i])
卖出:f[i][j]=max(q[k][1]-jxb[i])
再用单调队列维护就行
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int t, f[2001][2001], q[100010][2], a[2001], b[2001], as[2001], bs[2001];
int main()
{scanf("%d", &t);while(t--){int w, t, maxp;scanf("%d%d%d", &t, &maxp, &w);for(int i=0; i<=2000; i++)for(int j=0; j<=2000; j++)f[i][j]=-2147483647;//初始化for(int i=1; i<=t; i++)scanf("%d%d%d%d", &a[i], &b[i], &as[i], &bs[i]);for(int i=1; i<=w+1; i++)for(int j=0; j<=as[i]&&j<=maxp; j++)f[i][j]=-j*a[i];//因为1-w+1这几天没有可用的前驱，所以直接让他们成为w+1-t的前驱for(int i=1; i<=t; i++){for(int j=0; j<=maxp; j++)f[i][j]=max(f[i][j], f[i-1][j]);//假设这一天什么都不做int head=1, tail=0;if(i<=w+1)continue;int s=i-w-1;for(int j=0; j<=maxp; j++){int sum=f[s][j]+j*a[i];while(head<=tail&&sum>q[tail][1])tail--;q[++tail][0]=j;q[tail][1]=sum;while(head<=tail&&j-q[head][0]>as[i])head++;f[i][j]=max(f[i][j], q[head][1]-j*a[i]);//买入}head=1, tail=0;for(int j=maxp; j>=0; j--){int sum=f[s][j]+j*b[i];while(head<=tail&&sum>q[tail][1])tail--;q[++tail][0]=j;q[tail][1]=sum;while(head<=tail&&q[head][0]-j>bs[i])head++;f[i][j]=max(f[i][j], q[head][1]-j*b[i]);//卖出}}int ans=0;for(int j=0; j<=maxp; j++)ans=max(ans, f[t][j]);printf("%d\n", ans); }return 0;
}