题目详情 - [cqoi2012] 局部极小值 - BZOJ by HydroOJ
-
这题不值得单独写一个博客的，但我竟然没想出来，所以还是写吧 \(QwQ\)
-
又是我不擅长的找性质。性质：从小到大填数。当一个非局部最小值周围的所有局部最小值格子都被填了数时，这个位置才能填数。
-
然后就很简单了，状压 \(dp\) 即可
-
设计状态：\(dp_{i,S}\) 表示填了前 \(i\) 个数，局部最小值格子的状态为 \(S\) 的方案数
-
转移：\(dp_{i,S}=\sum\limits_{x\in S} dp_{i-1,S-x}+dp_{i-1,S}\)，其中前面求和项指第 \(i\) 个数填给一个局部最小值格子的方案数，后面这项指填非局部最小值的方案数。当然注意真正实现的时候要判断每个非局部最小值格子能否被填
-
-
复杂度 \(O(2^cnmc)\)，其中 \(c\) 为局部最小值格子个数，显然 \(c\leq 8\)
-
注意到非局部最小值题目要求强制不满足条件，但我们这么算是可能出现满足情况的，因此考虑再套一个容斥。
-
我们要枚举局部最小值格子的集合，因此复杂度会多一个 \(2^d\)，其中 \(d\leq 8\)
-
最终复杂度 \(O(2^{cd}nmc)\)，但是跑不满(搜索=玄学)