算r,h,l每个点只会被算一次所以是加上去的不是乘上去的
或者你看while里面总共跑n次,所以和外面的for无关,不就摊掉了吗
剩下就是枚举维度了
by itisover @ 2022-09-27 21:39:23
@[cqbzjtl](/user/434056) OI wiki 上的代码本质上是一个类似单调栈的东西,你可以结合单调栈分析复杂度的方式证明它是 $O(nm)$ 的。
此外悬线法还有一个类似 dp 的做法,你可以看[这份代码](https://www.luogu.com.cn/paste),很容易分析出它是 $O(nm)$ 的。
by 一扶苏一 @ 2022-09-27 21:42:25
@[一扶苏一](/user/65363) 未知代码
by itisover @ 2022-09-27 21:43:52
@[S11EDG](/user/186045)
https://www.luogu.com.cn/paste/8yl47jtu
by 一扶苏一 @ 2022-09-27 21:52:54
@[S11EDG](/user/186045) @[一扶苏一](/user/65363) 谢谢
by cqbz_gm @ 2022-09-27 23:36:06