合併 - histcat

問題#

黒板に $n$ 個の数が書かれており、小明は毎回連続した $k$ 個の数を選び、それらを黒板から消去し、それらの排他的論理和の値を元の位置に書き込みます。

小明はこの操作を行い、黒板に残るのが 1 つの数になるまで続けます。すべての操作の中で、黒板に最後に残る数の合計の最小値はいくらですか。

$n-1$ が $k-1$ の倍数であることが保証されており、必ず 1 つの数になるまで操作できます。

$100%$ のデータに対して、$2 \leq n \leq 500$、$2 \leq k \leq 50$、$0 \leq a_i \leq 1023$ が満たされます。

解答#

まず、k==2 の特別な場合を考え、単純な区間 dp であることがわかります。

次に、k!=2 の場合に拡張すると、2 次元の状態を表現するのが難しいことがわかり、1 次元を追加します。f[i][j][c] は、区間 i--j 内で ちょうど c 個の区間から 1 つの数字を合成するのに必要な最小コストを表します。

遷移を考えます。

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)$ を満たす必要があり、これにより最終的に 1 つの数字を合成できることが保証されます。

したがって、時間計算量は $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;
}