合併 - histcat

題目#

黑板上寫著一行 $n$ 個數，小明每次可以選擇連續的 $k$ 個數，將它們從黑板上擦去，並把它們的異或值寫到黑板上它們原來所在的位置上。

小明會這樣操作，直至黑板上只剩下一個數。請問在所有的使得黑板上最後只剩下一個數的操作方案中，小明寫下數字之和的最小值是多少。

保證 $n-1$ 是 $k-1$ 的倍數，也即一定可以操作至只剩下一個數。

對於 $100%$ 的數據，滿足 $2 \leq n \leq 500$，$2 \leq k \leq 50$，$0 \leq a_i \leq 1023$。

題解#

首先考慮k==2的特殊情況，發現為簡單的區間 dp

然後拓展到k!=2時，發現二維狀態難以表示，於是乎加上一維，設f[i][j][c]表示i--j這個區間內，最終由恰好c個區間合成一個數字，所需的最少代價

考慮轉移

f_{i,j,c}=min^{r-1}_{j=l} f_{l,j,1}+f_{j+1,r,c-1}

雖然狀態中的c只分割到 1 和 c-1，但是其包含了剩餘的情況

但是是 $O (n^3k)$ 的時間複雜度，過不了，考慮去除冗雜的狀態

合法的區間必須滿足 $(k-1)|(r-l+1-c)$，這樣才能夠保證其能最終合成一個數字

於是時間複雜度便成了 $O (\frac {n^3}{k})$，可以過

代碼#

#include<bits/stdc++.h>

using namespace std;

const int N = 505;
int a[N], xsum[N];
int n, k;
int f[N][N][N];//代表從i到j由c個區間合成，所能導致的最小代價 

int dfs(int l, int r, int c)
{
	if(l == r)
	{
		if(c == 1) return 0;
		else return 0x3f3f3f3f;
	}
	if(c == 1) c = k;
	if(f[l][r][c] != -1) return f[l][r][c];

	int ans = 0x3f3f3f3f;
	for(int i = l;i < r;i += (k - 1)) ans = min(ans, dfs(l, i, 1) + dfs(i + 1, r, c - 1));
	if(c == k) ans += xsum[r] ^ xsum[l - 1];
	return f[l][r][c] = ans;
}

int main()
{
    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);
	memset(f, -1, sizeof f); 
	scanf("%d%d", &n, &k);
	for(int i = 1;i <= n;i++) cin >> a[i], xsum[i] = xsum[i - 1] ^ a[i];

	printf("%d", dfs(1, n, 1));
	return 0;
}