标签：P3989 max 字母 leq 阶乘 dp SHOI2013
P3989
bzoj #4416
- 先考虑部分分，看到 \(n \leq 20\) 容易想到这个部分可以用状压
- 起初可以设 \(dp_{S,i}\) 表示在前 \(i\) 个数中选出集合 \(S\) 中的字母是否可行，转移即枚举下一个字母是什么
- 这个 dp 有一个很显然的性质：他肯定是前缀一段 \(0\) ，后缀一段 \(1\) 。我们不妨优化一下：设 \(dp_S\) 表示选完集合 \(S\) 中的数的所有情况中距离最远的情况能选择的最近下标是什么。
- 转移即记录 \(nxt_{i,j}\) 表示从 \(i\) 开始往后选第 \(j\) 个字母的最近距离，可以知道 \(dp_{S} = \max\limits_{x \notin S} \{ nxt_{dp_{S-x}+1,x} \}\)
- 最终答案即为 \([dp_{2^m-1} \leq n]\)
- 然后 \(n \leq 26\) 呢？我们发现比较优秀的构造方案是 \(abcdcbabcd \cdots\) 这样，他的长度下界应该是 \(n^2-n+1\) 的。我们发现当 \(n=22\) 时， \(n^2-n+1=463>450\) ，因此我们在 \(n \geq 22\) 时输出
NO 即可
- 最终复杂度 \(O(T|S|2^{\max(n,\omega)})\) ，其中 \(\omega=21\)
标签：P3989,
max,
字母,
leq,
阶乘,
dp,
SHOI2013
From： https://www.cnblogs.com/fox-konata/p/17790998.html