萌新的一点小疑惑

P2704 [NOI2001] 炮兵阵地

龙神哈迪斯 @ 2018-11-06 17:29:20

这题的复杂度难道是

O(n*2^m*2^m*2^m)

时间怎么可能过得去

有哪位大佬愿意帮萌新算一下...

by StudyingFather @ 2018-11-06 17:31:20

@龙神哈迪斯 事实上没有那么高，因为不合法的转移事实上不少。

by StudyingFather @ 2018-11-06 17:31:59

这些转移都会被跳过，所以实际计算的状态还是在可以接受的范围内。

by star_magic_young @ 2018-11-06 17:32:26

@龙神哈迪斯 合法状态可以预处理出来,数量不多

by 龙神哈迪斯 @ 2018-11-06 17:56:14

谢谢@StudyingFather

by 龙神哈迪斯 @ 2018-11-06 17:56:28

怎么预处理，真不会啊qaq

@star_magic_young

by star_magic_young @ 2018-11-06 19:09:41

@龙神哈迪斯 就是枚举所有可能的二进制状态,吧合法的保存起来

by 龙神哈迪斯 @ 2018-11-06 19:30:28

没事，当我傻了

@star_magic_young

by 龙神哈迪斯 @ 2018-11-06 19:30:50

我直接从1.5s+到0.047s...

还不开O2

|