BZOJ1855: [Scoi2010]股票交易（洛谷P2569）

BZOJ1855: [Scoi2010]股票交易（洛谷P2569）

单调队列 DP

BZOJ题目传送门
洛谷题目传送门

设 f [ i ] [ j ] f[i][j] f[i][j]表示前 i i i天还剩 j j j股的最多钱数。有四种转移方式。

1.之前没有股票，直接从这一天开始买， f [ i ] [ j ] = − j ∗ A P i ( j ∈ [ 0 , A S i ] ) f[i][j]=-j*AP_iquad(jin[0,AS_i]) f[i][j]=−j∗APi​(j∈[0,ASi​])

2.这一天啥也不干， f [ i ] [ j ] = f [ i − 1 ] [ j ] ( j ∈ [ 0 , M a x P ] ) f[i][j]=f[i-1][j]quad(jin[0,MaxP]) f[i][j]=f[i−1][j](j∈[0,MaxP])

3.之前有股票，且这一天也买， f [ i ] [ j ] = m a x { f [ i − w − 1 ] [ k ] − ( j − k ) A P i } (