先进行一遍DP，求出f[i][j]表示第i层取j本书的最大价值和，这个DP利用前缀和可以优化成 $O(N^{3})$ 。↵
然后再进行一遍DP，求出g[i][j]表示前i层取j本书的最大价值和，这个DP也是 $O(N^{3})$ 的。↵
↵
~~~~~↵
#include<iostream>↵
#include<cstdio>↵
#include<cstring>↵
#include<cmath>↵
#include<algorithm>↵
#include<vector>↵
using namespace std;↵
inline int read()↵
{↵
int x=0,f=1; char ch=getchar();↵
while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}↵
while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}↵
return x*f;↵
}↵
#define size(i) s[i].size()-1↵
vector<int>s[110],sum[110];↵
int f[110][10010],g[110][10010],N,M;↵
int main()↵
{↵
for (int i=1; i<=100; i++) s[i].push_back(0),sum[i].push_back(0);↵
N=read(),M=read();↵
for (int x,i=1,len,j; i<=N; i++) ↵
for (len=read(),j=1; j<=len; j++)↵
x=read(),s[i].push_back(x),sum[i].push_back(sum[i][j-1]+s[i][j]);↵
for (int i=1; i<=N; i++)↵
for (int j=1; j<=size(i); j++)↵
for (int k=1; k+size(i)-j-1<=size(i); k++)↵
f[i][j]=max(f[i][j],sum[i][size(i)]-(sum[i][k+size(i)-j-1]-sum[i][k-1]));↵
// for (int i=1; i<=N; i++,puts(""))↵
// for (int j=1; j<=size(i); j++)↵
// printf("%d ",f[i][j]);↵
for (int i=1,j,len=0; i<=N; i++)↵
for (len+=size(i),j=1; j<=len; j++)↵
for (int k=0; k<=size(i); k++)↵
if (j>=k && len-(size(i))>=j-k)↵
g[i][j]=max(g[i][j],g[i-1][j-k]+f[i][k]);↵
// for (int i=1; i<=N; i++,puts(""))↵
// for (int j=1; j<=size(i); j++)↵
// printf("%d ",g[i][j]);↵
printf("%d\n",g[N][M]);↵
return 0;↵
}↵
~~~~~
然后再进行一遍DP，求出g[i][j]表示前i层取j本书的最大价值和，这个DP也是 $O(N^{3})$ 的。↵
↵
~~~~~↵
#include<iostream>↵
#include<cstdio>↵
#include<cstring>↵
#include<cmath>↵
#include<algorithm>↵
#include<vector>↵
using namespace std;↵
inline int read()↵
{↵
int x=0,f=1; char ch=getchar();↵
while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}↵
while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}↵
return x*f;↵
}↵
#define size(i) s[i].size()-1↵
vector<int>s[110],sum[110];↵
int f[110][10010],g[110][10010],N,M;↵
int main()↵
{↵
for (int i=1; i<=100; i++) s[i].push_back(0),sum[i].push_back(0);↵
N=read(),M=read();↵
for (int x,i=1,len,j; i<=N; i++) ↵
for (len=read(),j=1; j<=len; j++)↵
x=read(),s[i].push_back(x),sum[i].push_back(sum[i][j-1]+s[i][j]);↵
for (int i=1; i<=N; i++)↵
for (int j=1; j<=size(i); j++)↵
for (int k=1; k+size(i)-j-1<=size(i); k++)↵
f[i][j]=max(f[i][j],sum[i][size(i)]-(sum[i][k+size(i)-j-1]-sum[i][k-1]));↵
// for (int i=1; i<=N; i++,puts(""))↵
// for (int j=1; j<=size(i); j++)↵
// printf("%d ",f[i][j]);↵
for (int i=1,j,len=0; i<=N; i++)↵
for (len+=size(i),j=1; j<=len; j++)↵
for (int k=0; k<=size(i); k++)↵
if (j>=k && len-(size(i))>=j-k)↵
g[i][j]=max(g[i][j],g[i-1][j-k]+f[i][k]);↵
// for (int i=1; i<=N; i++,puts(""))↵
// for (int j=1; j<=size(i); j++)↵
// printf("%d ",g[i][j]);↵
printf("%d\n",g[N][M]);↵
return 0;↵
}↵
~~~~~
