算法1

(多重背包) $O(n^2 * m)$

对每个队列预处理一个mx[i][j]:从第i个队列中取j个元素，最大元素和
可通过枚举从左端取元素数量来计算每一个mx[i][j],复杂度O(n^3)
剩下的就是将每个队列看做一组物品，取多少个元素看做体积，枚举从当前队列中取多少个元素，进行dp转移即可

C++ 代码

#include <bits/stdc++.h>
#define int long long 
#define INF 0x3f3f3f3f
#define fr first
#define se second
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int N = 2e5 + 10;

int n,m;
int c[110];
int sum[110][110];//队列的前缀和数组
int mx[110][110];
int dp[110][10010];//dp[i][j]表示从前i个队列中取j个元素，最大元素和
//ans = dp[n][m]

void solve()
{
    cin>>n>>m;
    vector<deque<int>> deq(110);
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        for(int j=1;j<=c[i];j++)
        {
            int x; cin>>x;
            deq[i].push_back(x);
            sum[i][j]=sum[i][j-1]+x;
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=c[i];j++)//要弹几个元素
        {
            for(int l=0;l<=j;l++)//从左端取l个元素 , 右端j-l个元素
            {
                mx[i][j]=max(mx[i][j],sum[i][l]+(sum[i][c[i]]-sum[i][c[i]-(j-l)]));
            }
        }
    }

    for(int i=1;i<=n;i++)//第i个队列
    {
        for(int j=m;j>=0;j--)//取j个元素
        {
            dp[i][j]=dp[i-1][j];//不从第i个队列中取元素
            for(int k=1;k<=min(j,c[i]);k++)//从第i个队列中取k个元素
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j-k]+mx[i][k]);
            }
        }
    }

    cout<<dp[n][m]<<endl;
}


signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1; //cin>>T;
    while(T--) solve();
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla