Description

KC来到了一个盛产瓷器的国度。他来到了一位商人的店铺。在这个店铺中，KC看到了一个有n(1<=n<=100)排的柜子，每排都有一些瓷器，每排不超过100个。那些精美的艺术品使KC一下心动了，决定从N排的商品中买下m(1<=m<=10000)个瓷器。 这个商人看KC的脸上长满了痘子，就像苔藓一样，跟精美的瓷器相比相差太多，认为这么精致的艺术品被这样的人买走艺术价值会大打折扣。商人感到不爽，于是规定每次取商品只能取其中一排的最左边或者最右边那个，想为难KC。 现在KC又获知每个瓷器的价值（用一个不超过100的正整数表示），他希望取出的m个商品的总价值最大。

Input

输入文件的第一行包括两个正整数n,m; 接下来2到n+1行，第i行第一个数表示第i排柜子的商品数量Si，接下来Si个数表示从左到右每个商品的价值。

Output

输出文件只有一个正整数，即m个商品最大的总价值。

Sample Input

输入1： 2 3 3 3 7 2 3 4 1 5 输入2： 1 3 4 4 3 1 2

Sample Output

输出1： 15 样例解释1： 取第一排的最左边两个和第二排的最右边那个。总价直为3+7+5=15； 输出2： 9

Data Constraint

对于10%的数据，$S_i=1,1<=i<=n$。 对于另外10%的数据，$n=1$.

Analysis

有$n$行，$n\in [1,100]$，每行个数有可能不同。一共购买$m$个物品，$m\in [1,10000]$每行可以购买前$i$个物品和后$j$个物品，$i,j\in [0,100]$

Solution

容易发现，每行的最优都可以单独预处理算出，而当每行购买$i$个商品的最大价值确定后，就可以转换为一个多重背包问题。 于是预处理每一行的购买$i$件商品的最大价值。

$设在该行一共有s个商品，购买k个商品，在左边购买m个商品，则在右边购买k-m个商品$ 容易得到： $val[k]={\sum }_{m=0}^k({\sum }_{i=1}^{m}va{l}_i+{\sum }_{j=s-(k-m)+1}^{s}va{l}_j)$

当然，区间和我们可以用简单的前缀和算出：

for(int i = 1;i<=s;++i)//处理前缀和为以后求区间和做准备 sum[i] = sum[i-1] + val[i];

于是上式可以简化成：

$设s个商品在左边取了m个，在右边取了k-m个$ $val[k]=su{m}_m+su{m}_s-su{m}_{s-(k-m)}$ 前缀和求区间和：$su{m}_{[i,j]}=su{m}_j-su{m}_{i-1}$

由于数据量小，可以直接枚举这个m，得到此时的最大价值。 那么我们就可以用O(s)的复杂度预处理，随后用O($s^2$)的复杂度求出该商品购买所有件数时的最大价值。 其中$s\in [1,100]$，有$n$种商品，$n\in [1,100]$，每种都需要$O(s^2)$进行预处理，复杂度可能达到$O(n{s}^2)$但由于常数很小，还是可以接受的。

for(register int k = 1;k<=n;++k)//第k种 for(register int i = 1;i<=s[k][0];++i) //表示取i个的时候,s[k][0]代表该商品总个数 for(register int j = 0;j<=i;++j) dp[k][i] = MAX(dp[k][i],\ sum[k][j] + sum[k][s[k][0]] - sum[k][s[k][0] - i + j]);

接下来就是多重背包问题了: $有n种商品，每种商品有p_i个，第i种商品取j个得到的最大价值为s_{ij}，$ $每个商品的体积都为1，容量为m，问最多能取得多大价值。$

//dp[i][j]代表在第i行取j个商品的最大获利 //f[i][j]代表在前i行取j个商品 for(register int i = 1;i<=n;++i) //在第i行选商品 for(register int j = 1;j<=m;++j)//此时一共选择j个商品 for(register int k = 0;k<=s[i][0] && k <= j;++k) { //k是在这一行取得多少商品，注意k不能超过当前取商品量 //当前在前i行取j个商品，在当前行取k个商品，那么就在前i-1行取j-k个商品 dp[i][j] = MAX(dp[i][j],dp[i-1][j-k] + f[i][k]); }

本题结束。

Code

#include <cstdio> #define MAX(x,y) ((x)>(y)?(x):(y)) using namespace std; void read(int &r) { static char c; for(c=getchar();c>'9'||c<'0';c=getchar()); for(;c<='9'&&c>='0';r=(r<<1)+(r<<3)+c-48,c=getchar()); } int n,m; int s[105][105]; int dp[105][10005];//表示从第i排取出j个的最大价值和 int f[105][105]; int sum[105][105]; int main() { read(n); read(m); for(register int i = 1;i<=n;++i) { read(s[i][0]); for(register int j = 1;j<=s[i][0];++j) read(s[i][j]); } for(register int i = 1;i<=n;++i)//处理前缀和为以后求区间和做准备 for(register int j = 1;j<=s[i][0];++j) sum[i][j] = sum[i][j-1] + s[i][j]; //每行按行dp算出取n个商品时的最大值 for(register int k = 1;k<=n;++k) for(register int i = 1;i<=s[k][0];++i) //表示取i个的时候 for(register int j = 0;j<=i;++j) f[k][i] = MAX(f[k][i],sum[k][j] + sum[k][s[k][0]] - sum[k][s[k][0] - i + j]); //在左边取j个，右边取 i - j个 //使用前缀和的方法求区间 //f[i][j]代表在第i行取j个商品的最大获利 //dp[i][j]代表在前i行取j个商品 for(register int i = 1;i<=n;++i) //在第i行选商品 for(register int j = 1;j<=m;++j)//此时一共选择j个商品 for(register int k = 0;k<=s[i][0] && k <= j;++k) { //k是在这一行取得多少商品，注意k不能超过当前取商品量 //当前在前i行取j个商品，在当前行取k个商品，那么就在前i-1行取j-k个商品 dp[i][j] = MAX(dp[i][j],dp[i-1][j-k] + f[i][k]); } printf("%d",dp[n][m]); return 0; }