CF1442D Sum

CF1442D Sum

tony102

2021 年 02 月 18 日

1193 次浏览

暂无评论

726字数

题解

[Link](https://www.luogu.com.cn/problem/CF1442D)

## Sol

贪心策略：除了一个数组不选完外，其余的数组全部选完为最优。

那么现在怎么样来选择数组。假如是全部都是选整个数组的话，我们把数组长度看成体积，整个数组的和看成价值做背包即可。现在的问题是，我们有一个数组不能全部选满，怎么做？

采用分治的办法解决。是不是我们可以把所有数组分成两项来合并答案，当我们递归进单个数组的时候对这个数组进行背包，更新答案。否则我们可以先把每次分治的左边的数组全部选满，做一次背包。拷贝下当前的dp数组，来算那个不选满的数组出现在右边的答案。再同样处理左边即可。

## Code
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 3e3 + 5;

int n, k, res;
int f[SIZE], tot[SIZE];
std::vector < int > a[SIZE];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

void dp(int x) {
	int len = tot[x];
	for (int i = k; i >= len; -- i) f[i] = std::max(f[i], f[i - len] + a[x][len]);
}

void sol(int l, int r) {
	if (l == r) {
		for (int i = 1; i <= std::min(k, tot[l]); ++ i) res = std::max(res, f[k - i] + a[l][i]);
		return;
	}
	int mid = (l + r) >> 1, tmp[SIZE];
	memset(tmp, 0, sizeof(tmp));
	for (int i = 0; i <= k; ++ i) tmp[i] = f[i];
	for (int i = l; i <= mid; ++ i) dp(i);
	sol(mid + 1, r);
	for (int i = 0; i <= k; ++ i) f[i] = tmp[i];
	for (int i = mid + 1; i <= r; ++ i) dp(i);
	sol(l, mid);
	for (int i = 0; i <= k; ++ i) f[i] = tmp[i];
}

signed main() {
	// freopen("code.in", "r", stdin);
	n = read(), k = read();
	for (int i = 1; i <= n; ++ i) {
		tot[i] = read(), a[i].push_back(0);
		for (int j = 1, x; j <= tot[i]; ++ j) {
			x = read(), a[i].push_back(a[i][j - 1] + x);
		}
	}
	sol(1, n);
	printf("%lld\n", res);
	return 0;
}
```

最后修改：2021 年 08 月 20 日