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;
}

526互联

CF1442D-Sum

Sum

solution

code