zcmimi's blog

arrow_back单调队列共14篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f[i][j]表示第i天有j只股票最多赚多少钱 \\

  1. 直接买 f[i][j] = -ap[i] \times j
  2. 不买不卖

    f[i][j] =f[i-1][j]

  3. 买股

    f[i][j] = f[i-w-1][k] - ap[i] \times (j-k) (j-as[i] \le k \le j)

  4. 卖股

    f[i][j] = f[i-w-1][k] + bp[i] \times (k-j) (j \le k \le j + bs[i])

但是这样还是O(n^3)的复杂度,得想办法降到O(n^2)

看一下f[i][j] = f[i-w-1][k] - ap[i] \times (j-k) (j-as[i] \le k \le j)

可以化为f[i][j] = (f[i-w-1][k] + ap[i] \times k) - ap[i] \times j (j-as[i] \le k \le j)

于是就可以单调队列了 OωO

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

单调队列优化dp

f[i]表示从1-i最多能选出的效率

枚举断点j,

f[i] = \max(f[j-1]+ \sum_{t=j+1}^i a[t])

但是直接这样的复杂度不可行

我们可以考虑用单调队列优化

f[i] = \max(f[j-1] - S_j) + S_i

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

二分

判断的时候枚举区间,用rmq或单调队列来求最值,还可以用堆(看题解的)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_{t,i,j} = MAX(f_{t-1,x',y'})+1

复杂度:O(Tnm),只能过50%

看到k \le 200那么我们是不是可以直接用?

f_{k,i,j}为在区间k中在位置(i,j)能最多滑行多远

f_{k,i,j} = MAX(f_{k-1,i,j},f_{k-1,i',j'}+dis_{(i,j),(i',j'))})

那么复杂度就是O(kn^3),可以用单调队列优化掉其中一个n

2/2
Search
search