AcWing 5969. 最大元素和

问题描述

给定 n 个双端队列，其中第 i 个队列内有 cᵢ 个整数元素。

现在，你需要进行 m 次弹出操作。

每次操作你可以任意选定一个队列，并将其头部或尾部的元素弹出。

我们希望弹出的 m 个元素的和尽可能大。

请你计算并输出这个最大元素和。

输入格式

• 第一行包含两个整数 n 和 m。
• 接下来 n 行，其中第 i 行用来描述第 i 个双端队列，首先包含一个整数 cᵢ，表示该队列内的元素数量，然后包含 cᵢ 个整数，表示该队列内的元素。

输出格式

输出一个整数，表示最大元素和。

数据范围

• 前三个测试点满足 1 ≤ n ≤ 2。
• 所有测试点满足：
  • 1 ≤ n ≤ 100
  • 1 ≤ m ≤ 10000
  • 1 ≤ cᵢ ≤ 100
  • 队列内元素的取值范围 [1, 100]
  • 所有队列的元素总数至少为 m

输入样例 1

2 3
3 3 7 2
3 4 1 5

输出样例 1

15

输入样例 2

1 3
4 4 3 1 2

输出样例 2

9

c++代码

#include<bits/stdc++.h>
#include<stdio.h>

using namespace std;

int n, m, k, ans = 0;
vector<vector<int>> w;
vector<int> last, now;

int main() {
    scanf("%d %d", &n, &m);
    w = vector<vector<int>>(n + 1);
    last = vector<int>(m + 1), now = vector<int>(m + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &k);
        vector<int> mid(k + 1);
        for (int j = 1; j <= k; j++) {
            scanf("%d", &mid[j]);
            mid[j] += mid[j - 1];
        }
        int c = min(m, k), sum = mid[k] - mid[0];
        w[i] = vector<int>(c + 1);
        for (int j = 0; j <= c; j++) {
            int len = (k - j);
            for (int a = 1; a + len - 1 <= k; a++) w[i][j] = max(w[i][j], sum - (mid[a + len - 1] - mid[a - 1]));
        }
    }
    for (int i = 1; i <= n; i++) {
        int c = w[i].size() - 1;
        for (int k = 0; k <= c; k++) {
            for (int j = k; j <= m; j++) now[j] = max(now[j], w[i][k] + last[j - k]);
        }
        last = now;
    }
    printf("%d", last[m]);
    return 0;
}//by wqs