CF1442D - Sum

自己的想法

这种题大概有两种办法：

• 贪心
• 动态规划
• 网络流？

首先思考贪心。

• 考虑怎样选一定不会更劣。但是考虑不出来啊？
• 考虑选最大数。选目前最大数的前提条件是把最大数之前的都选了。这样就未必是最优的了。
  反悔贪心。真的能反悔吗？？

考虑网络流？

• 首先源点向某个点连边。流量为 \(k\) ，费用为0.
• 然后每个数组的每个数，它前一个向他连边，流量为 1，费用为这个数的权值。
• 每个数向汇点连边，费用为 0，流量为 1
• 不过这样好像没限制是否只能走 \(k\) 个点。

考虑动态规划？

• 不过应该有个暴力好像。
• 设 \(s_{i,j}\) 表示第 \(i\) 个序列的前 \(j\) 个数的和为 \(s_{i,j}\)。然后再进行一波 \(\text{dp}\) ，设 \(g_{i,j}\) 表示前 \(i\) 个序列，选了 \(j\) 个数最大权值，枚举第 \(i\) 个序列选了多少个有转移：\(g_{i,j}=\max_{k=0}^j\{g_{i-1,j-k}+f_{i,k}\}\) 。这样的话复杂度是 \(\mathcal O(nk^2)\) 的。

思考这个问题的特征是什么

• 它告诉你这个序列是不降序列。

最终还是没想出来。

题解

结论

有一个结论：必然至多存在一个序列满足这里面只选了一个数。

如果有两个序列 \(a_x\) 和 \(a_y\) 都没有全选，设 \(a_{x,1}\sim a_{x,p}\) 都选了并且 \(a_{y,1}\sim a_{y,q}\) 都选了。不妨设 \(a_{x,p+1}>a_{y,q+1}\) ，那么 \(\sum_{i=1}^k a_{x,p+k}\ge \sum_{i=1}^ka_{y,q-i+1}\) 。即将 \(a_{y,q-k+1}\sim a_{y,q}\) 换为 \(a_{x,p+1}\sim a_{x,p+k}\) 这些数和不会更差。所以必然存在一种选法满足最多一个序列没有选满。

做法

那么只要枚举每个序列当成没有选满的序列，然后其他序列跑背包。

如何求出去掉每个数后的 \(\text{dp}\) 数组？

考虑分治。分治树是一颗线段树，相当于在 \(\text{dfs}\) 一棵线段树。用一个 \(\text{dp}\) 数组，在刚 \(\text{dfs}\) 到这个结点的时候，\(\text{dp}\) 数组的值应该是去掉这个节点所代表的区间，剩下的所有数计算出的 \(\text{dp}\) 数组。每次 \(\text{dfs}\) 到他的两个子节点，会先加上右边一半再 \(\text{dfs}\) 左边，再从初始状态加上左边一半 \(\text{dfs}\) 右边一半。

代码

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const long long NN = 3e3 + 5, NK = 3e3 + 5;
long long N, K, len[NN], f[NN], ans;
vector<long long> seq[NN];
void Upd(long long siz, long long val) {
	for (long long i = K; i >= siz; --i) {
		f[i] = max(f[i], f[i - siz] + val);
	}
}
void Divide(long long L, long long R) {
	if (L == R) {
		for (long long i = 0; i <= min((long long)len[L], K); ++i)
			ans = max(ans, f[K - i] + seq[L][i]);
		return ;
	}
	long long mid = (L + R) / 2;
	long long rec[NK];
	for (long long i = 0; i <= K; ++i)
		rec[i] = f[i];
	for (long long i = mid + 1; i <= R; ++i)
		Upd(len[i], seq[i][len[i]]);
	Divide(L, mid);
	for (long long i = 0; i <= K; ++i)
		f[i] = rec[i];
	for (long long i = L; i <= mid; ++i)
		Upd(len[i], seq[i][len[i]]);
	Divide(mid + 1, R);
}
int main() {
	freopen("sum.in", "r", stdin);
	freopen("sum.out", "w", stdout);
	scanf("%lld%lld", &N, &K);
	for (long long i = 1; i <= N; ++i) {
		scanf("%lld", &len[i]);
		seq[i].push_back(0);
		for (long long j = 1; j <= len[i]; ++j) {
			long long x;
			scanf("%lld", &x);
			seq[i].push_back(x);
		}
		for (long long j = 1; j <= len[i]; ++j)
			seq[i][j] = seq[i][j - 1] + seq[i][j];
	}
	memset(f, 0x8f, sizeof(f));
	f[0] = 0;
	Divide(1, N);
	printf("%lld\n", ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

复盘

需要先想到暴力，然后再想到结论，再用优化。

暴力很容易想。

可以发现如果暴力 \(g_{i,j}\) 转移的时候可以去掉枚举的复杂度，那么就不会TLE。或许这样就可以想到，如果真的每个数组要么都选，要么不都选了。这可能需要一些突发奇想，才能想到这个结论吧。

优化其实可以这样想。先想到去掉每个数后的问题有很多相同部分。然后想到用分治利用共同部分？

CF1442D - Sum

原文：https://www.cnblogs.com/YouthRhythms/p/13978589.html