Sol
贪心策略:除了一个数组不选完外,其余的数组全部选完为最优。
那么现在怎么样来选择数组。假如是全部都是选整个数组的话,我们把数组长度看成体积,整个数组的和看成价值做背包即可。现在的问题是,我们有一个数组不能全部选满,怎么做?
采用分治的办法解决。是不是我们可以把所有数组分成两项来合并答案,当我们递归进单个数组的时候对这个数组进行背包,更新答案。否则我们可以先把每次分治的左边的数组全部选满,做一次背包。拷贝下当前的dp数组,来算那个不选满的数组出现在右边的答案。再同样处理左边即可。
Code
#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;
}