题意翻译

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

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

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

输入格式

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

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

输出格式

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

Input & Output 's examples

Input 's eg 1

2 3
3 3 7 2
3 4 1 5

Output 's eg 1

15

Input 's eg 2

1 3
4 4 3 1 2

Output 's eg 2

9

数据范围与约定

对于的数据，保证,,。

分析

一道毒瘤的区间。

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

考虑使用前缀和维护。设表示第行中前个物品的价值总和，很容易得到后个物品的价值为。其中为第行的物品数量。

之后我们设为在第行中拿出个物品的最大价值。易得状态转移方程$$

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

很简单，我们设表示从前行中拿出个物品的最大价值。则我们可得状态转移方程$$

其中，需要进行枚举，时间复杂度为，足以通过本题。

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

转移时请按照顺序转移，不要随意改变转移顺序(来自考场上随便改变转移顺序而只得了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;
}

THE END