#549. 【UNR #4】序列妙妙值

UOJ 比赛的质量果然很高。（我没做出来只能说我的实力还不行）

40pts:（暴力）

状态 (f_{i,j}) 表示把前 (i) 个数分成 (j) 段的最小代价（异或和之和），随便转移一下就好。复杂度 (O(n^2k))。

60pts

看到 (k) 很小，并且值域不大，考虑把值带到状态里加速 DP。异或是可以“相减”的，因此我们可以设 (g_{i,j,s}) 表示前 (i) 个数分成 (j) 段，且 (1 ... i) 的异或和为 (s) 的最小代价。为了方便转移，我们设 (f_{i,j,s}) 表示考虑了前 (k) 个数，目前已经分成 (j) 段（后面还没分），且 (1 ... p_j) 的异或和为 (s) 的最小代价（其实就是 (g) 的最小值）。这样有转移：

[f_{i,j,s}gets f_{i-1,j,s} ]

[f_{i,j,xor} gets f_{i-1,j-1,s} + (s oplus xor) ]

其中 (xor) 表示当前的前缀异或和。第一个式子是不分段，第二个式子是在 (i) 这里分一段。答案就从第二个式子的更新值中找即可。

发现第一个式子就是继承，因此可以直接滚动数组不清空直接用即可。

复杂度：(O(nka_i))。瓶颈在于第二个转移式子。

100pts

既然有 (a_i le 2^8) 的部分分，那么 (a_i le 2^{16}) 应该就是把 16 劈成两半处理。

很容易想到我们设个状态为 (f_{i,j,s1,s2})，表示前八位为 (s1)，后八位为 (s2) 的最小代价，转移的时候分别取最小；并且显然这个算法是错误的，因为我们不能保证两个取最小的决策点相同。

那么怎么办？我们找到最小值后 (O(1)) 修改是不是太快了？想到一般数据结构都有 (log) 修改 (log) 查询的平衡复杂度思想，我们这里是否也可以 (log) 修改 (log) 查询？不知道，但是这里有一个根号的算法。

我们设 (f_{i,j,s1,s2}) 表示考虑前 (i) 个数，已经分了 (j) 段，前八位异或和为 (s1)，后八位已经准备好给 (s2) 了的最小代价。这样，我们查询时 (s2) 确定，修改时 (s1) 确定，这样就可以把复杂度优化到 (O(nk sqrt a_i)) 了。

转移方程：（用 (t1,t2) 表示 (xor) 的前八位和后八位）

[Ans_{i,j} gets f_{i-1,j-1,s_1,t_2} + s_1 oplus t_1 ]

[f_{i,j,t_1,s_2} gets Ans_{i,j} + s_2 oplus t_2 ]

关键代码：

const int mask = 255, base = 8;
for (register int s = 0; s <= mask; ++s)	f[0][0][s] = s;
int Xor = 0;
for (register int i = 1; i <= n; ++i) {
	int a; read(a); Xor ^= a;
	int t1 = Xor >> base, t2 = Xor & mask;
	for (register int j = K; j; --j) {
		int tmp = inf;
		for (register int s1 = 0; s1 <= mask; ++s1)
			MIN(tmp, f[j - 1][s1][t2] + ((s1 ^ t1) << base));
		for (register int s2 = 0; s2 <= mask; ++s2) 
			MIN(f[j][t1][s2], tmp + (t2 ^ s2));
		if (i >= K && j == K)	printf("%d ", tmp);
	}
}

zzzyyds!

zbkaknoi!!