如果你 T 了好好想想你的复杂度能不能过
查看原帖
如果你 T 了好好想想你的复杂度能不能过
174045
FZzzz楼主2022/10/19 16:41

我估计不会有第二个我这样的傻逼犯这种睿智错误……

总之就是,如果你的时间复杂度是单组数据 O(nmc22m)O(nmc^22^m),然后想都没想直接开冲了,那你可能会像我一样疑惑一万年自己常数为什么这么大……

实际上你状压只需要压后 mc+1m-c+1 位,那其实复杂度要除掉一个 2c2^c,由于 c22c\dfrac{c^2}{2^c} 渐进意义上是 O(1)O(1) 的所以实际上复杂度就是 O(nm2m)O(nm2^m)

2022 年 10 月 19 日,面对 P3290,FZzzz 使出全身解数仍无济于事,最终……我编不下去了,总之警钟长鸣。

2022/10/19 16:41
加载中...