menu zcmimi's blog

arrow_back 单调队列

相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串

那么我们差分之后再判断即可 ```cpp

include<bits/stdc++.h>

define gc get

zc
2020-05-16 21:36

首先用后缀数组求出height数组

可以发现,重复出现的子串在sa数组中一定是连续的

那么在height中也是连续的

那么我们只需要求出 height数组中 连续k-1个数中 最小的数 最大

zc
2020-05-16 14:13

预处理出二维前缀和

预处理出每个以(i,j)为右下角的A*B矩阵的和

预处理出每个以(i,j)为右下角的C*D矩阵的和

先用单调队列出列的C*D的最小值

再用另一个单调队列处理出行的

zc
2019-12-21 19:47

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

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

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

f_{k,i,j}为在区

zc
2019-12-21 19:47

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

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

    $f[i][j] =f

zc
2019-12-21 19:47

单调队列优化dp

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

枚举断点j,

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

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

zc
2019-12-21 19:47

二分

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

include<bits/stdc++.h>

namespace ZDY{

#pragma G
zc
2019-12-21 19:47

题目大意:

给定一个长度为 n\leq 500000 的序列 a_1, a_2, \cdots, a_n ,要求对于每一个 1 \leq r \leq n ,找到最小的非负整数 $

zc
2019-12-21 19:47

显而易见:

f_i = f_j + [ a_i \le a_j ] (i < j \le n)

题目要求是复杂度O(nq)

一看有个步伐限制

那么显然加个单调队列就完事了

```cp

zc
2019-12-21 19:47

首先要知道选定一个区间首先要减去的是最大的连续d区间的和

可以用单调队列维护当前区间最大连续长度为d的子区间和

我们可以发现如果[l,r]合法,那么[l+1...r,r]都合法

zc
2019-12-21 19:47
1 / 2
Search
search