[luoguP2569] [SCOI2010]股票交易(DP + 单调队列)
阅读原文时间:2025年02月03日阅读:1

传送门

$f[i][j]$ 表示第i天,手中股票数为j的最优解

初始化 $f[i][0]=0$ $0<=i<=n$

4种方式转移

  1. 以前没买过,第i天凭空买 $f[i][j]=-j*ap$
  2. 第i天什么都不干 $f[i][j]=f[i-1][j]$
  3. 第i天买 $f[i][j]=f[i-w-1][k]-(j-k)*as=f[i-w-1][k]+k*as-j*as$
  4. 第i天卖 $f[i][j]=f[i-w-1][k]+(k-j)*bs=f[i-w-1][k]+k*bs-j*bs$

可以将 $f[i-w-1][k]+k*as$ 和 $f[i-w-1][k]+k*bs$ 放到单调队列中

#include
#include
#include
#define N 3001

using namespace std;

int n, m, w, ap, bp, as, bs, t, h, ans;
int f[N][N], q[N];

inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
}

int main()
{
int i, j;
n = read();
m = read();
w = read();
memset(f, -127, sizeof(f));
for(i = 0; i <= n; i++) f[i][0] = 0; for(i = 1; i <= n; i++) { ap = read(); bp = read(); as = read(); bs = read(); for(j = 1; j <= as; j++) f[i][j] = -ap * j; for(j = 0; j <= m; j++) f[i][j] = max(f[i][j], f[i - 1][j]); if(i - w - 1 >= 0)
{
h = 1, t = 0;
for(j = 0; j <= m; j++) { while(h <= t && f[i - w - 1][q[t]] + q[t] * ap < f[i - w - 1][j] + j * ap) t--; q[++t] = j; while(h <= t && q[h] < j - as) h++; f[i][j] = max(f[i][j], f[i - w - 1][q[h]] + q[h] * ap - j * ap); } h = 1, t = 0; for(j = m; j >= 0; j--)
{
while(h <= t && f[i - w - 1][q[t]] + q[t] * bp < f[i - w - 1][j] + j * bp) t--; q[++t] = j; while(h <= t && q[h] > j + bs) h++;
f[i][j] = max(f[i][j], f[i - w - 1][q[h]] + q[h] * bp - j * bp);
}
}
}
for(i = 0; i <= m; i++) ans = max(ans, f[n][i]);
printf("%d\n", ans);
return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章