前缀异或建模。
设前缀异或 p[i] = a1 xor a2 xor … xor ai(p[0]=0)。把数组划分为若干连续子段,对应的是选取分割点 0=i0<i1<…<im=n,第 k 段的异或值为
s_k = p[ik] xor p[ik-1]。因此问题化为:在前缀序列 p[0..n] 上选点,使相邻点的“异或差”序列 s1..sm 构成**驼峰(交替上升/下降)**序列,且段数 m 最大。
值域仅 0..255 的关键性质。
因为 ai∈[0,255],任意前缀异或 p[i] 也在 0..255。这使得可以用“值压缩 DP”,在每个前缀值上聚合最优状态,从而把状态数量限制在常数级(256)。
给定一个长度为 n 的整数数组 {a1,a2,...,an},其中每个元素 ai 的取值范围为 0≦ai≦255 ;
你需要将该数组划分为若干个互不相交的非空连续子段,这些子段按照在原数组中的顺序排列后,其按位异或 (xor) 结果必须构成一个驼峰序列;
求最多可以划分出多少个这样的子段。