标签：leftarrow sum 4069 Apio2015 按位 dp bzoj
bzoj #4069
- 二进制？按位考虑。
- 或操作而且最小？按位贪心。
- 从最高位往下贪，记录一个 \(x\) 表示当前最高位确定了哪些位可以为 \(0\) (其中存在为 \(0\) 方案的位上值为 \(1\) )
- 考虑 dp 处理对于第 \(t\) 位能否为 \(0\) ：
- 设计状态：设 \(dp_{i,j}\) 表示前 \(i\) 个数分成 \(j\) 个部分后**在满足高位满足 \(x\) 限制条件的情况下能否取到。
- 初始化：\(dp_{i,j} \leftarrow 0, dp_{0,0} \leftarrow 1\)
- 转移：当 \((sum[i]-sum[k])\& x=0\) 时 \(dp_{i,j} \leftarrow dp_{k,j-1}\)
- 记录答案：\(Ans = \max_{i=A}^B dp_{n,i}\)
- 最终复杂度 \(O(n^3\log A)\) ，显然过不了最后一个数据
- 发现当 \(A=1\) 时我们只用判断右端点的情况，显然是越低越好。让 \(dp_i\) 记录前 \(i\) 个数最少分成多少个部分满足答案即可，优化掉一个 \(O(n)\)
标签：leftarrow,
sum,
4069,
Apio2015,
按位,
dp,
bzoj
From： https://www.cnblogs.com/fox-konata/p/17794733.html