题意
已知t天的股票走势(买入卖出价格),且每天买入卖出股数有限制,总共持有的股数也有限制,连续两次交易(买入卖出各算一次)必须间隔w天。
求出最大净赚钱数。
思路
设f[i][j]为第i天交易后持有j张股票时的最大净赚钱数。
易得动态转移方程。
发现枚举的上一次交易后持有股数是随着j的增大下限而增大的,可以用单调队列进行优化。
至于上一次交易,我们选择第i-w-1天,因为前面天可以通过不买股票来转移到第i-w-1天。
代码
#include <deque>
#include <cstdio>
#include <cstring>
std::deque<int> q;
int t, maxp, w;
int f[2001][2001], ap[2001], bp[2001], as[2001], bs[2001];
int main() {
scanf("%d %d %d", &t, &maxp, &w);
for (int i = 1; i <= t; i++)
scanf("%d %d %d %d", &ap[i], &bp[i], &as[i], &bs[i]);
memset(f, 128, sizeof(f));
for (int i = 1; i <= t; i++) {
for (int j = 0; j <= as[i]; j++)
f[i][j] = -ap[i] * j;
for (int j = 0; j <= maxp; j++)
f[i][j] = std::max(f[i - 1][j], f[i][j]);
if (i <= w)
continue;
q.clear();//tmd
for (int j = 0; j <= maxp; j++) {
while (q.size() && j - q.front() > as[i])
q.pop_front();
while (q.size() && f[i - w - 1][j] + j * ap[i] >= f[i - w - 1][q.back()] + q.back() * ap[i])
q.pop_back();
q.push_back(j);
f[i][j] = std::max(f[i][j], f[i - w - 1][q.front()] - ap[i] * (j - q.front()));
}
q.clear();
for (int j = maxp; j >= 0; j--) {//倒序使得决策范围缩小
while (q.size() && q.front() - j > bs[i])
q.pop_front();
while (q.size() && f[i - w - 1][j] + j * bp[i] >= f[i - w - 1][q.back()] + q.back() * bp[i])
q.pop_back();
q.push_back(j);
f[i][j] = std::max(f[i][j], f[i - w - 1][q.front()] + bp[i] * (q.front() - j));
}
}
for (int i = 0; i <= maxp; i++)
f[t][maxp] = std::max(f[t][maxp], f[t][i]);
printf("%d", f[t][maxp]);
}