第一个单调队列优化dp
写了半天，最后初始化搞错了还一直wa。。
题目大意：
炒股，总共 t 天，每天可以买入na[i]股，卖出nb[i]股，价钱分别为pa[i]和pb[i]，最大同时拥有p股
且一次交易后至少要间隔w天才能再次交易，初始有0股，本金无限，求最大收益
题解：
dp[i][j]表示第 i 天，有 j 股的最大收益
状态转移 dp[i][j]=max{dp[i-1][j](不买不卖)，dp[r][k]-(j-k)*pa[i]（i-r>w,j-k<=na[i]，买），dp[r][k]+(k-j)*pb[i]（i-r>w,k-j<=nb[i]，卖）}
复杂度 为 t*t*p*p
首先我们可以看出 dp[i][j]>=dp[i-1][j]（不买不卖转移）
所以可以将 r 确定为 i-w-1，复杂度变为t*p*p 还是很大
然后对于买，移项有
dp[i][j]+j*pa[i]=dp[r][k]+k*pa[i]。右边与 j无关， 可见我们只需要对每一个 i 维护一个关于k的单调队列，就可以在 p时间内求出所有的dp[i][j]
复杂度降为 t*p 可以接受了
最后注意下边界条件：
1到w+1的都是从初始条件下转移的
代码：
#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define MAXN 2000
#define inf 200000000
int na[MAXN+],nb[MAXN+],pa[MAXN+],pb[MAXN+];
int dp[MAXN+][MAXN+];
int t,p,w;
typedef struct Node
{
int val,num;
}node;
typedef struct dqueue
{
node q[MAXN*];
int l,r;
bool empty()
{
return l==r;
}
void clear()
{
l=;r=;
}
node front()
{
return q[l];
}
void pop()
{
l++;
}
void push(node x)
{
if(l==r)
{
q[r++]=x;
return;
}
if(x.val>q[l].val)
{
r=l;
q[r++]=x;
return;
}
for(int i=r;i>l;i--)
{
if(x.val<q[i-].val)
{
r=i;
break;
}
}
q[r++]=x;
}
}Dqueue;
Dqueue qa,qb;
int buy(int now,int n)
{
node tmp;
while()
{
tmp=qa.front();
if(tmp.num<n-na[now])
{
qa.pop();
}
else
break;
}
return tmp.val;
}
int sale(int now,int n)
{
node tmp;
while()
{
tmp=qb.front();
if(tmp.num<n)
{
qb.pop();
}
else
break;
}
return tmp.val;
}
void DP()
{
for(int i=;i<=t;i++)
{
for(int j=;j<=p;j++)
{
dp[i][j]=-inf;
}
}
node no;
for(int i=;i<=w+;i++)
{
for(int j=;j<=na[i];j++)
{
dp[i][j]=-pa[i]*j;
}
for(int j=;j<=p;j++)
{
dp[i][j]=max(dp[i][j],dp[i-][j]);
}
}
for(int i=w+;i<=t;i++)
{
qa.clear();
qb.clear();
int r=i-w-; //上一次交易的天数
for(int j=;j<nb[i];j++)
{
no.num=j;
no.val=dp[r][j]+j*pb[i];
qb.push(no);
}
for(int j=;j<=p;j++)
{
no.num=j;
no.val=dp[r][j]+j*pa[i];
qa.push(no);
if(j+nb[i]<=p)
{
no.num=j+nb[i];
no.val=dp[r][j+nb[i]]+(j+nb[i])*pb[i];
qb.push(no);
}
dp[i][j]=max(dp[i][j],dp[i-][j]); //不买
int tmp=buy(i,j);
dp[i][j]=max(dp[i][j],tmp-j*pa[i]); //买
tmp=sale(i,j);
dp[i][j]=max(dp[i][j],tmp-j*pb[i]); //卖
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&t,&p,&w);
for(int i=;i<=t;i++)
{
scanf("%d%d%d%d",pa+i,pb+i,na+i,nb+i);
}
DP();
int ans=;
for(int i=;i<=p;i++)
{
ans=max(ans,dp[t][i]);
}
printf("%d\n",ans);
}
return ;
}