Merge - histcat

Problem#

On the blackboard, there is a line of $n$ numbers. Xiao Ming can choose $k$ consecutive numbers each time, erase them from the blackboard, and write their XOR value back to the position where they originally were on the blackboard.

Xiao Ming will perform this operation until only one number remains on the blackboard. What is the minimum sum of the numbers that Xiao Ming writes down among all the operation schemes that leave only one number on the blackboard?

It is guaranteed that $n-1$ is a multiple of $k-1$, which means it is always possible to operate until only one number remains.

For $100%$ of the data, it satisfies $2 \leq n \leq 500$, $2 \leq k \leq 50$, $0 \leq a_i \leq 1023$.

Solution#

First, consider the special case of k==2, which turns out to be a simple interval dynamic programming.

Then, when extending to k!=2, it is found that a two-dimensional state is difficult to represent, so an additional dimension is added. Let f[i][j][c] represent the minimum cost required to combine exactly c intervals into one number within the interval i--j.

Consider the transition:

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

Although the state c only splits into 1 and c-1, it includes the remaining cases.

However, the time complexity is $O(n^3k)$, which is not feasible, so consider removing redundant states.

A valid interval must satisfy $(k-1)|(r-l+1-c)$, which ensures that it can ultimately combine into one number.

Thus, the time complexity becomes $O(\frac{n^3}{k})$, which is feasible.

Code#

#include<bits/stdc++.h>

using namespace std;

const int N = 505;
int a[N], xsum[N];
int n, k;
int f[N][N][N];//represents the minimum cost of combining c intervals from i to j 

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;
}