menu zcmimi's blog

arrow_back 四边形不等式

f[i][j]表示前i个分j个邮局

f[i][j]=\min(f[x][j-1]+w[x+1][i])

满足决策单调性

```cpp

include<bits/stdc++.h

zc
2020-01-18 22:40

详见四边形不等式优化

最小值有单调性,可以使用四边形不等式优化

但是最大值没有

但是最大值有个性质:

一定是一直把其他石子合并到某堆石子

那么我们可以$f[l][r]=\max(

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

题目大意:

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

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