https://www.acwing.com/problem/content/334/
第一次写单调队列优化的dp，首先朴素的做法不难想到，就是复杂度 \(O(n^3)\) ，然后考虑优化。
每天都从 \(pre=max(0,i-w-1)\) 天转移过来就刚刚好了。
考虑每个k是怎么更新j的。
买入股票：
\(dp[i][j]=max\{dp[pre][k]-(j-k)*AP_i\;|\;k \leq j\;and\;(j-k) \leq AS_i\}\)
\(dp[i][j]=max\{dp[pre][k]+k*AP_i\;|\;k \leq j\;and\;(j-k) \leq AS_i\}-j*AP_i\)
里面的这个k的取值范围随j的增长会滑动，所以用单调队列维护。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dp[2005][2005];
deque<int> AQ, BQ;
int AP, BP;
ll Calc_A(int id1, int id2) {
return dp[id1][id2] + 1ll * id2 * AP;
}
ll Calc_B(int id1, int id2) {
return dp[id1][id2] + 1ll * id2 * BP;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
int T, maxP, W;
scanf("%d%d%d", &T, &maxP, &W);
memset(dp, -INF, sizeof(dp));
dp[0][0] = 0;
for(int i = 1; i <= T; ++i) {
for(int j = 0; j <= maxP; ++j)
dp[i][j] = dp[i - 1][j];
int AS, BS;
scanf("%d%d%d%d", &AP, &BP, &AS, &BS);
AQ.clear(), BQ.clear();
int pre = max(0, i - W - 1);
int Ak = 0;
for(int j = 0; j <= maxP; ++j) {
while(Ak <= j) {
ll tmp = Calc_A(pre, Ak);
while(!AQ.empty() && Calc_A(pre, AQ.back()) <= tmp)
AQ.pop_back();
AQ.push_back(Ak);
++Ak;
}
while(!AQ.empty() && (AQ.front() < j - AS))
AQ.pop_front();
if(!AQ.empty())
dp[i][j] = max(dp[i][j], Calc_A(pre, AQ.front()) - 1ll * j * AP);
//cout<<AQ.size()<<endl;
}
int Bk = maxP;
for(int j = maxP; j >= 0; --j) {
while(Bk >= j) {
ll tmp = Calc_B(pre, Bk);
while(!BQ.empty() && Calc_B(pre, BQ.back()) <= tmp)
BQ.pop_back();
BQ.push_back(Bk);
--Bk;
}
while(!BQ.empty() && (BQ.front() > BS + j))
BQ.pop_front();
if(!BQ.empty())
dp[i][j] = max(dp[i][j], Calc_B(pre, BQ.front()) - 1ll * j * BP);
//cout<<BQ.size()<<endl;
}
/*for(int j = 0; j <= maxP; ++j) {
printf("dp[%d][%d]=%lld\n", i, j, dp[i][j]);
}
puts("");*/
}
ll ans = -INF;
for(int i = 0; i <= maxP; ++i) {
ans = max(ans, dp[T][i]);
}
printf("%lld\n", ans);
}