[luoguP2569] [SCOI2010]股票交易（DP + 单调队列）

传送门

$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[i1][j]$
3. 第i天买 $f[i][j]=f[iw1][k](jk)*as=f[iw1][k]+k*asj*as$
4. 第i天卖 $f[i][j]=f[iw1][k]+(kj)*bs=f[iw1][k]+k*bsj*bs$

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

#include <cstdio>#include <cstring>#include <iostream>#define N 3001using namespace std;int n, m, w, ap, bp, as, bs, t, h, ans;int f[N][N], q[N];inline int read()int main()h = 1, t = 0;for(j = m; j >= 0; j)}}for(i = 0; i <= m; i++) ans = max(ans, f[n][i]);printf("%d\n", ans);return 0;}

上一篇：[luoguP2325] [SCOI2005]王室联邦（树分块乱搞）

下一篇：[luoguP3317] [SDOI2014]重建（矩阵树定理）