十分普通的DP+不平凡的转移
这道题状态十分明显。转移是(O(n^4))的，过不去，我们需要优化。
一个十分显然的DP是(f(i,j))表示第(i)天时候拥有(j)单位股票的最大收益。(可以小于零)。它的转移方式是：
(f(i,j)=max(f(k,b)+(b-j) imes sell[t] or(buy[t])))
此时，我们发现一个转移需要两重循环，也就是(O(n^2))，加上右边的式子，就是(O(n^4))的。
考虑优化：
-
对于转移方程，发现我们可以进行参变量分离。对状态转移方程进行代数变形。
-
- (RHS=max(f(k,b)+b imes sell[t]-j imes sell[t]))
-
- (j)在转移时，是最开始那个等式的(LHS)，可以提前确定，从(max)拿出来。
-
- (RHS=max(f(k,b)+b imes sell[t])-j imes sell[t])
-
- 于是，对于(max(f(k,b)+b imes sell[t]))，可以拿数据结构维护了。
-
对于转移方法，我们只需要从(f(i-W-1,j) , jle maxP)转移过来就好了。这一定是最优的那个状态，比它要早的状态一定会$le f(i-W-1,j) $。
-
- 因为这个（晚的）状态在转移的时候，考虑过 从比他 (早的) 状态直接转移过来，于是(f(i-W-1,j))不小于前面那个。
于是，我们可以将(f(i-W-1,b) ,ble maxP)的所有状态压入某个数据结构。我们发现，对于这种数据结构的要求是：
- 维护最大值
- 可以清理过期状态（买入卖出股票有多少限制）
- 重置方便
就是单调队列吃饭的本领。
一句话解释单调队列：一个状态比你小（限制条件少）还比你强（数值大），那么你就被淘汰了。
单调队列是(O(n))的，枚举(LHS)的(i)是(O(n))的。总复杂度(O(n^2))，可以过了。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<bitset>
#include<vector>
#include<map>
#include<ctime>
#include<cstdlib>
#include<set>
#include<bitset>
#include<stack>
#include<list>
#include<cmath>
using namespace std;
#define RP(t,a,b) for(register ll (t)=(a),edd_=(b);t<=edd_;++t)
#define DRP(t,a,b) for(register ll (t)=(a),edd_=(b);t>=edd_;--t)
#define ERP(t,a) for(int t=head[a];t;t=e[t].to)
#define Min(a,b) ((a)<(b)?(a):(b))
#define TMP template<class ccf>
typedef long long ll;
TMP inline ccf qr(ccf k){
char c=getchar();
ccf x=0;
int q=1;
while(c<48||c>57)
q=c==45?-1:q,c=getchar();
while(c>=48&&c<=57)
x=x*10+c-48,c=getchar();
if(q==-1)
x=-x;
return x;
}
const int maxn=2e3+15;
inline void Swap(ll& a,ll& b){
ll k=a;
a=b;
b=k;
}
ll buy[maxn];
ll sell[maxn];
ll buytimes[maxn];
ll selltimes[maxn];
ll n,maxP,W;
ll dp[maxn][maxn];
int q[maxn];
TMP inline ccf Max(ccf a,ccf b){
if(a<b)
return b;
return a;
}
inline void init(){
memset(dp,-0xf,sizeof dp);
RP(t,1,n){
buy[t]=qr(1ll);
sell[t]=qr(1ll);
buytimes[t]=qr(1ll);
selltimes[t]=qr(1ll);
}
RP(t,1,n){
int head=1,tail=0;
if(t-W-1>0){
//trade
DRP(i,maxP,0){
while(head<=tail&&q[head]>i+selltimes[t])
head++;
while(head<=tail&&
dp[t-W-1][q[tail]]+1ll*q[tail]*sell[t]
<=dp[t-W-1][i]+1ll*i*sell[t]
)
--tail;
q[++tail]=i;
if(head<=tail)
dp[t][i]=max(dp[t][i],dp[t-W-1][q[head]]+(q[head]-i)*sell[t]*1ll);
}
//purchase
head=1,tail=0;
RP(i,0,maxP){
while(head<=tail&&q[head]<i-buytimes[t])
++head;
while(head<=tail&&
dp[t-W-1][q[tail]]+q[tail]*buy[t]
<=dp[t-W-1][i]+i*buy[t])
--tail;
q[++tail]=i;
if(head<=tail)
dp[t][i]=Max(dp[t][i],dp[t-W-1][q[head]]+(q[head]-i)*buy[t]*1ll);
}
}
//restart
RP(i,0,maxP){
dp[t][i]=Max(dp[t][i],dp[t-1][i]);
if(i<=buytimes[t])
dp[t][i]=Max(dp[t][i],-i*buy[t]);
}
}
ll ans=0;
RP(t,0,maxP)
ans=max(ans,dp[n][t]);
cout<<ans<<endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
while(~scanf("%lld%lld%lld",&n,&maxP,&W))
init();
return 0;
}