[BZOJ4069][Apio2015]巴厘岛的雕塑

题目大意

分成 (x) 堆，是的每堆的和的异或值最小

分析

这是一道非常简单的数位 (DP) 题

基于贪心思想，我们要尽量让最高位的 (1) 最小， 因此我们考虑从高位向低位进行枚举，看是否存在一种方案使得最高为不为 (1)，如果不存在，那就填 (1)

因此我们要解决如下问题：

1. 保存之前的状态
2. 考虑 (A), (B) 的限制

我们设已经考虑到 (x) 位，并且当前的值为 (ans)

显然如果该位可以不填，它必须满足存在一种状态使得之前已经决定的状态的异或和为 (ans)， 并且新增的一段不会使得 (ans) 改变
那这就是一个经典的区间DP问题
我们不妨设 (f[i][j]) 表示前 (i) 个数分成 (j) 段，是否存在这一种情况
如果满足上述条件，我们就能够从 (f[k][j - 1]) 转移到 (f[i][j])

对于每个一位，如果有一种给情况使得当前为为0，那就让 (ans) 的当前位为 (0)

复杂度：(O(n^3logD))

对于最后一组数据：(A =1, B le n)，段数只有上限
我们要想把 (f) 数组的第二个维度省掉的话，用 (f[i]) 记录将前 (i) 个数分段并得到可行解的最小段数，最后判断其是否小于 (B)，即可
复杂度：(O(n^2logD))

总结

想了半天发现 (O(n^3logD)) 没办法优化，结果发现最后一个点的 (A = 1)。

const int maxn = 2018;

typedef long long LL;
LL s[maxn];
int f[maxn][maxn], g[maxn];
LL ans = 0, t;
int n, A, B, len = 0;

bool valid(LL val, int dig) {
    return ((val >> (LL)dig | ans) == ans && (val & 1LL << (LL)dig-1LL) == 0);
}

void work1() {
	for(int x = len; x > 0; -- x) {
		forn(i, n) g[i] = INF;
		forn(i, n) Forn(j, i) if (g[j] < B) {
            t = s[i] - s[j];
            if(valid(t, x)) if (g[j] + 1 < g[i]) g[i] = g[j] + 1;
        }
		ans <<= 1LL;
		if(g[n] > B) ans ++;
	}
}

void work2() {
	for(int x = len; x > 0; -- x) {
		memset(f, 0, sizeof(f));
		f[0][0] = 1;
		forn(i, n) forn(j, i) for (int k = 0; k < i; ++ k) if(f[k][j-1]) {
            t = s[i] - s[k];
			//printf("x = %d i = %d j = %d k = %d t = %d
", x, i, j, k, t);
            if(valid(t, x)) f[i][j] = 1;
		}
		int i;
		for(i = A; i <= B; ++ i) {
			if(f[n][i]) break;
		}
		ans <<= 1LL;
		if(i > B) ans ++;
	}
}

int main() {
	read(n, A, B);
	forn(i, n) {
		read(s[i]); s[i] += s[i-1];
	}
	len = (int)log2(s[n]) + 1;
	if (A == 1) work1();
	else work2();
	printf("%lld", ans);
	return 0;
}