浅谈缺一分治

这个思想好像并不常见，我也是一个月前在 lxr 讲 dp 的课上第一次听说这个名字，后来 ACM 比赛中出了一个 gym 题，也可以运用相同的思想，但是脑子短路没搞出来，现在随便记一记。

缺一分治，顾名思义，就是在题目中有一个位置的限制和其它位置不一样，我们利用分治的思想，枚举每一个位置，然后把 \(O(n)\) 的部分优化到 \(O(\log n)\)。

给个典题，也是 lxr 讲的：CF1442D sum

给定 \(n\) 个不降的数组。有一个值 \(ans\)，初始为 \(0\)。你需要进行如下操作 \(k\) 次：选择一个数组，把 \(ans\) 加上数组的第一个元素，之后把它删除。

请求出 \(ans\) 最大是多少，所有数组的元素总个数 \(\leq 10^6\)，\(n,k\leq 3000\)。

首先这题有一个很重要的性质，没有这个性质就谈不上运用缺一分治：

至多有一个序列没被选满。

这个证明用微调法证一下即可，具体可以看这篇题解。

然后就可以用上我们的缺一分治了，我们先求出每个序列的总和，设 \(f(l,r)\) 表示选择一部分的那个序列在 \([l,r]\) 区间内，选出的最大值，然后我们进行分治。

我们先把 \([l,mid]\) 序列做一个背包 DP，然后递归 \([mid+1,r]\)；然后撤销贡献，把 \([mid+1,r]\) 序列做一个背包 DP，然后递归 \([l,mid]\)。就这样，一直到 \(l = r\) 时，此时的这个序列就是我们的“一”，也就是没选满的这个，我们可以枚举它选了几个，然后更新我们的答案。显然，最后 \(f(1,n)\) 便是我们要求的答案。

需要注意的我们撤销贡献的方法是在递归的时候多加一维度 \(col\)，表示当前分治到了第几层，然后我们撤销贡献的时候就把它赋值成上一层的值即可。

这样本来是 \(O(nk^2)\) 的算法，就被我们优化到 \(O(nk\log n)\) 了。

核心代码:

il void dfs(int l,int r,int col)//col表示当前是第几层
{
	if(l == r)
	{
	//考虑部分取的数组在 [l,r] 中的最优解。
	//如果 l<r，先把 [mid+1,r] 中的元素加入背包，递归计算 [l,mid]，再把背包复原，把 [l,mid] 中的元素加入背包，递归计算 [mid+1,r] 。
	//这样一个nk^2的算法，我们只需要logk层，就可以 nklogn的复杂度内求出来了
		for(re int i=min(k,cnt[l]);i>=0;i--)
			ans = max(ans,f[k-i][col] + a[l][i]);
		return ;
	}
	int mid = (l+r) >> 1;
	for(re int i=0;i<=k;i++) f[i][col+1] = f[i][col];
	for(re int i=mid+1;i<=r;i++)
		for(re int j=k-cnt[i];j>=0;j--) f[j+cnt[i]][col+1] = max(f[j+cnt[i]][col+1],f[j][col+1]+sum[i]);
	dfs(l,mid,col+1);
	for(re int i=0;i<=k;i++) f[i][col+1] = f[i][col];
	for(re int i=l;i<=mid;i++)
		for(re int j=k-cnt[i];j>=0;j--) f[j+cnt[i]][col+1] = max(f[j+cnt[i]][col+1],f[j][col+1]+sum[i]);
	dfs(mid+1,r,col+1);
}

signed main()
{
	n = read() , k = read();
	for(re int i=1;i<=n;i++)
	{
		cnt[i] = read() , a[i].push_back(0);
		for(re int j=1;j<=cnt[i];j++)
		{
			x = read() , sum[i] += x;
			a[i].push_back(sum[i]);
		}
	}
	dfs(1,n,0);
	cout << ans;
	return 0;
}

总之，缺一分治就是把那个特殊的留在最后，同时处理出不特殊的部分的贡献，然后分治往下找的过程。

还有一个 ACM 出上的 gym 题：Gym-104090C No Bug No Game

这个题你同样可以知道，只有一个序列不会取最后一个数，而其他的都是取最后一个数的，然后你就可以对这个不取最后一个数的位置进行缺一分治，然后这样做大约也是 \(O(nk\log n)\) 的，可以比较极限的通过，正解是 \(O(nkp)\) 的。

核心代码：

il void dfs(int l,int r,int col)
{
	if(l == r)
	{
		ans = max(ans,f[k][col]);
		for(re int i=1;i<=min(k,w[l]);i++)
			ans = max(ans,f[k-i][col] + v[l][i]);
		return ;
	}
	int mid = (l+r) >> 1;
	for(re int i=0;i<=k;i++) f[i][col+1] = f[i][col];
	for(re int i=mid+1;i<=r;i++)
		for(re int j=k;j>=w[i];j--) f[j][col+1] = max(f[j][col+1],f[j-w[i]][col+1]+v[i][w[i]]);
	dfs(l,mid,col+1);
	for(re int i=0;i<=k;i++) f[i][col+1] = f[i][col];
	for(re int i=l;i<=mid;i++)
		for(re int j=k;j>=w[i];j--) f[j][col+1] = max(f[j][col+1],f[j-w[i]][col+1]+v[i][w[i]]);
	dfs(mid+1,r,col+1);
}

signed main()
{
	n = read() , k = read();
	int Max = 0;
	for(re int i=1;i<=n;i++)
	{
		w[i] = read(); 
		sump += w[i];
		for(re int j=1;j<=w[i];j++)
			v[i][j] = read() , Max = max(Max,v[i][j]);
		sumw += v[i][w[i]];
	}
	memset(f , -0x3f , sizeof f);
	f[0][0] = 0;
	dfs(1,n,0);
	if(sump <= k) ans = max(ans,sumw);
	cout << ans;
	return 0;
}

这就是缺一分治的基本思想，目前我就只遇到了这两个题，如果有什么新花样还会补充。