题意翻译

有一个公主一生气就喜欢摔东西。

现在有很多个柜子，每个柜子里面装着很多物品，公主每次摔东西只能随机的选择一个柜子，拿出最左边或者最右边的一个物品摔碎，

给出公主最多生气的次数$m$，求生完气之后，公主摔掉物品的价值的最大总和。

输入格式

第一行输入$n$,$m$,$n$为柜子的层数，$m$为公主最多生气的次数。

接下来$n$行，每行第一个输入该层物品的数量$k$,接下来输入$k$个物品的价值$v_i$。

输出格式

输出仅有一个整数$ans$，表示公主摔掉物品的价值的最大总和。

Input & Output ‘s examples

Input ‘s eg 1

2 3
3 3 7 2
3 4 1 5

Output ‘s eg 1

Input ‘s eg 2

1 3
4 4 3 1 2

Output ‘s eg 2

数据范围与约定

对于$100\%$的数据，保证$1<=n<=100$,$1<=m<=10000$,$1<=k<=100$。

分析

一道~~毒瘤的~~区间$DP$。

首先，题目中规定只能取边上的物品。因此每次取完之后剩下的必然也是一个区间。

考虑使用前缀和维护。设$sum[i][j]$表示第$i$行中前$j$个物品的价值总和，很容易得到后$k$个物品的价值为$sum[i][num[i] - j]$。其中$num[i]$为第$i$行的物品数量。

之后我们设$dp[i][j]$为在第$i$行中拿出$j$个物品的最大价值。易得状态转移方程 $dp[i][j] = max(dp[i][j] , sum[i][k] + sum[i][num[i]] - sum[i][num[i] - (j - k)])$

这样我们就可以解决一行了。但是对于多行我们又该怎么办呐？

很简单，我们设$f[i][j]$表示从前$i$行中拿出$j$个物品的最大价值。则我们可得状态转移方程 $f[i][j] = max(f[i][j] , f[i - 1][j - k] + dp[i][k])$

其中，$i , j , k$需要进行枚举，时间复杂度为$O(n^3)$，足以通过本题。

如果还有什么的话，那就是

转移时请按照顺序转移，不要随意改变转移顺序~~(来自考场上随便改变转移顺序而只得了10分的作者)~~

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 101

using namespace std;

int n , m , num[N];

int dp[N][N];   //dp[i][j] 从第i行物品中拿出j个的最大价值
int f[N][10001];    //f[i][j] 从前i行拿出j个物品的最大价值和
int sum[N][N];   //sum[i][j] 第i行前j个物品的价值之和

int a[N][N];

//dp[i][j] = max_element(sum[i][k] + sum[i][n] - sum[i][n - (j - k)])

//f[i][j] = max(f[i][j] , f[i - 1][j - k] + dp[i][k])



int main(){
//	freopen("./porcelain1.in" , "r" , stdin);
    scanf("%d%d" , &n , &m);
    for(int i = 1; i <= n; i ++){
        scanf("%d" , &num[i]);      
        sum[i][0] = 0;
        for(int j = 1; j <= num[i]; j ++){
            scanf("%d" , &a[i][j]);
            sum[i][j] = a[i][j] + sum[i][j - 1];    //计算前缀和
        }
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= num[i]; j ++){
            for(int k = 0; k <= j; k ++){   //进行第一遍dp，处理单排情况
                dp[i][j] = max(dp[i][j] , sum[i][k] + sum[i][num[i]] - sum[i][num[i] - j + k]); 
            }
        }
    }
    for(int i = 1;  i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            for(int k = 0; k <= min(j , num[i]); k ++){     //进行第二遍dp，处理多排情况。
                f[i][j] = max(f[i][j] , f[i - 1][j - k] + dp[i][k]);
            }
        }
    }
    printf("%d" , f[n][m]);
    return 0;
}