设 $f_{i,j}$ 为前 $i$ 层取了 $j$ 个数的最大和。

若在第 $i$ 层和前 $(i-1)$ 层都有取数，且第 $i$ 层的数没有被取完，那么转移这一层的时候决策点是否单调？

放个代码：

#include<bits/stdc++.h>
#define il inline
#define ll long long
using namespace std;
const int maxn=5010;
il int read(){
	int x=0;
	char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
vector<ll>p[maxn];
int n,k,len[maxn];
ll f[maxn][maxn];
il void chkmax(ll &x,ll y){if(y>x)x=y;}
void calc(int t,int l1,int r1,int l2,int r2){
	if(l1>r1) return ;
	int mid=l1+r1>>1,id;
	if(mid<l2) return ;
	for(int i=l2;i<=min(r2,mid);i++)
		if(f[t-1][i]+p[t][min(mid-i,len[t])]>f[t][mid]) 
			f[t][mid]=f[t-1][i]+p[t][min(mid-i,len[t])],id=i;
	calc(t,l1,mid-1,id,r2),calc(t,mid+1,r1,l2,id);
}
int main(){
	memset(f,128,sizeof(f));
	n=read(),k=read();
	for(int i=1;i<=n;i++){
		len[i]=read(),p[i].push_back(0);
		for(int j=1;j<=len[i];j++) 
			p[i].push_back(read()),p[i][j]+=p[i][j-1];
	}
	for(int i=0;i<=k;i++) f[1][i]=p[1][min(i,k)];
	for(int i=2;i<=n;i++){
		calc(i,1,k,0,k);
		for(int j=0;j<=k;j++){
			chkmax(f[i][j],f[i-1][j]);
			chkmax(f[i][j],f[i-1][j-min(j,len[i])]+p[i][min(j,len[i])]);
		} 
			
	}
	printf("%lld\n",f[n][k]);
	return 0;
}

WA#12