Sum
You are given \(n\) non-decreasing arrays of non-negative numbers.
Vasya repeats the following operation \(k\) times:
- Selects a non-empty array.
- Puts the first element of the selected array in his pocket.
- Removes the first element from the selected array.
Vasya wants to maximize the sum of the elements in his pocket.
solution
1、通过微调。
首先在最终状态下，假设数组 \(a,b\) 中的元素分别被取到了 \(i,j\)（并没有取完），且 \(a_{i} \leq b_{j}\)。
由于数组内元素不降的性质，可以得知 \(a_{i-1} \leq a_{i}\)，那么 \(a_{i-1}\leq b_{j}\)。
可以之前发现取 \(a_{i-1}\) 是不一定比 \(b_{j}\) 优的。
因此可以得到一条结论：在最终状态下，最多只会存在一个数组 \(x\) 被取了部分。
2、冻柜
对于其他的数组，要么不选，要么全选。
那么就可以将其转化为 \(n\) 个具有大小、价值的物品，进行 \(01\) 背包。
枚举那个被取了部分的数组 \(x\)，枚举数组 \(x\) 被取出的元素的个数，时间复杂度为 \(n^2k\) 的。
3、分治优化
令 \(m = \left\lfloor\frac{l+r}{2}\right\rfloor\)。
在位于 \([l,m]\) 中的数组 \(x\)，都需要来自 \((m,r]\) 的数组的 dp 值。
那么对于 \([l,m]\) 中的数组 \(x\)，可以将 \((m,r]\) 的 dp 值预处理出来。
该过程可以递归操作，直到 \(l=r\) 的时候，对于第 \(l\) 个数组，需要的 dp 值是都已经求出来的。
时间复杂度降到 \(kn\log_2n\)。
code
点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<long long> a[3010];
long long dp[3010], sum[3010], len[3010], n, k;
long long DFS(int l, int r)
{
if (l == r) {
long long res = 0, ans = -1;
for (int i = 0; i <= min(k, len[l]); i ++ ) {
ans = max(ans, dp[k - i] + res);
if (i < len[l]) res += a[l][i];
}
return ans;
}
long long f[3010], mid = (l + r) >> 1, ans = -1;
memcpy(f, dp, sizeof(dp));
// 对于[l,mid]的数组，预处理(mid,r]的dp值
for (int i = mid + 1; i <= r; i ++ )
for (int j = k; j >= len[i]; j -- )
dp[j] = max(dp[j], dp[j - len[i]] + sum[i]);
ans = max(ans, DFS(l, mid)); // 递归
memcpy(dp, f, sizeof(f));
for (int i = l; i <= mid; i ++ )
for (int j = k; j > len[i]; j -- )
dp[j] = max(dp[j], dp[j - len[i]] + sum[i]);
ans = max(ans, DFS(mid + 1, r));
return ans;
}
int main()
{
scanf("%lld%lld", &n, &k);
for (int i = 1, x; i <= n; i ++ ) {
scanf("%lld", &len[i]);
for (int j = 1; j <= len[i]; j ++ ) {
scanf("%lld", &x);
a[i].push_back(x); sum[i] += x;
}
}
printf("%lld", DFS(1, n));
return 0;
}