Link.
Description.
有很多数组，保证递增。
对于每个数组你可以选出一个前缀，可以为空。
问总共选择 \(K\) 个数的总权值。
Solution.
对每个数组做前缀和，然后就成为下凸函数。
考虑下凸有什么性质。
设最终状态每个数组所在位置为 \(w_i\)，考虑调整。
我们每次找到两个 \(a,b\)，对其中一个左移 \(1\)，另一个右移 \(1\)。
最后状态肯定不能这样移动，且不充分。
考虑 \(a\) 不能左移的条件：\(a\) 左边斜率比 \(b\) 右边大。
同时 \(a,b\) 右边斜率比左边斜率大，所以肯定有 \(b\) 右边斜率比 \(a\) 左边斜率大。
这样就肯定可以右移。
所以这样就证明了要么整段不取，要么整段取。
（当然因为有 \(k\) 的限制，所以可能会剩下一段。
哈哈以上就是所有我自己想到的东西，接下来的 sb 背包不会做！！！
相当于我们需要用 \(O(n^3)\) 以下的复杂度求出去掉一个物品的背包。
可以考虑 \(O(n^2\sqrt n)\) 的分块，也可以考虑 \(O(n^2\log n)\) 的分治。
反正无论怎么做都行，但是我就是不会哈哈哈哈哈哈，小丑了。
Coding.
点击查看代码
//Coded by Kamiyama_Shiki on 2021.11.08 {{{
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=3005;int n,K,at[N],st[N],tp;
ll vl[N],a[N][N],tmp[1000005],dp[25][N],rs=0;
inline void solve(int l,int r,int id)
{
if(l==r)
{
for(int j=1;j<=at[l];j++) rs=max(rs,a[l][j]+dp[id][K-j]);
return;
}
int nx=st[tp--],md=(l+r)>>1;
for(int j=0;j<=K;j++) dp[nx][j]=dp[id][j];
for(int i=l;i<=md;i++) for(int j=K;j>=at[i];j--) dp[nx][j]=max(dp[nx][j],dp[nx][j-at[i]]+vl[i]);
solve(md+1,r,nx);for(int j=0;j<=K;j++) dp[nx][j]=dp[id][j];
for(int i=md+1;i<=r;i++) for(int j=K;j>=at[i];j--) dp[nx][j]=max(dp[nx][j],dp[nx][j-at[i]]+vl[i]);
solve(l,md,nx),st[++tp]=nx;
}
int main()
{
read(n,K);for(int i=1;i<=n;i++)
{
read(at[i]);for(int j=1;j<=at[i];j++) read(tmp[j]),tmp[j]+=tmp[j-1];
vl[i]=tmp[at[i]=min(K,at[i])];for(int j=1;j<=K;j++) a[i][j]=tmp[j];
}
for(int i=1;i<=24;i++) st[++tp]=i;
return solve(1,n,0),printf("%lld\n",rs),0;
}