做专业维修网站/产品经理培训哪个机构好

$Link$

$ssl1497$

$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

输出2：

9

$Hint$

样例解释1：
取第一排的最左边两个和第二排的最右边那个。总价直为3+7+5=15；
对于10%的数据，Si=1,1<=i<=n。
对于另外10%的数据，n=1.

$Solution$

前缀和 + DP
设$su{m}_{i,j}$为第i行前j个获得的价值
设$h_{i,j}$为第i行取j个获得的最大价值
那么转移就很容易得出：
$h[i][j]=max(h[i][j],sum[i][k]+sum[i][c[i]]-sum[i][c[i]-j+k])$
其实就是前缀和和后缀和之类的balabala的组合出来
然后单行的就处理好了
多行的就设一个$f[i][j]$表示前i行选j个的最大值
$f[i][j]=max(f[i][j],f[i-1][j-k]+h[i][k])$
k表示当前行选k个

$Code$

#include<iostream>
#include<cstdio>using namespace std;int n, m, s[105];
int sum[105][10005], h[105][10005], f[105][10005];int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i){int x;sum[i][0] = 0;scanf("%d", &s[i]);for (int j = 1; j <= s[i]; ++j)scanf("%d", &x),sum[i][j] = sum[i][j - 1] + x; }for (int i = 1; i <= n; ++i)for (int j = 1; j <= s[i]; ++j)for (int k = 0; k <= j; ++k)h[i][j] = max(h[i][j], sum[i][k] + sum[i][s[i]] - sum[i][s[i] - j + k]);for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)for (int k = 0; k <= min(j, s[i]); ++k)f[i][j] = max(f[i][j], f[i - 1][j - k] + h[i][k]);printf("%d\n", f[n][m]);return 0;
}