题目

题目描述

KC来到了一个盛产瓷器的国度。他来到了一位商人的店铺。在这个店铺中，KC看到了一个有n(1<=n<=100)排的柜子，每排都有一些瓷器，每排不超过100个。那些精美的艺术品使KC一下心动了，决定从N排的商品中买下m(1<=m<=10000)个瓷器。

这个商人看KC的脸上长满了痘子，就像苔藓一样，跟精美的瓷器相比相差太多，认为这么精致的艺术品被这样的人买走艺术价值会大打折扣。商人感到不爽，于是规定每次取商品只能取其中一排的最左边或者最右边那个，想为难KC。

现在KC又获知每个瓷器的价值（用一个不超过100的正整数表示），他希望取出的m个商品的总价值最大。

输入

输入文件的第一行包括两个正整数n,m;

接下来2到n+1行，第i行第一个数表示第i排柜子的商品数量Si，接下来Si个数表示从左到右每个商品的价值。

输出

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

样例

输入样例

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

输入2：
1 3
4 4 3 1 2

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

说明

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

思路

~~假思路：分类讨论~~

当S_i=1时，sort,前m大的和
当n = 1 时，枚举前面选多少个，后面选多少个
其余情况......

真思路：
其实想完n = 1时，离成功就不远了，仔细想想，发现可以把每一排的商品都拆开成每一组，如：{4,3,1,2}拆分为{4},{4,3},{4,3,1},{4,3,1,2},{4,2},{4,1,2}......
每一组都不能同时选多个（这不就是分组背包吗！）
然后打了一个“分组背包”,扔到样例1，对了
然后...然后就交了........再然后，就出事了（2AC（S_i=1和n=1的分）,3WA,5TLE）
原来是分组背包写错了（WA的30分）
再预处理一下每一排选i个的最大值，就AC了

反思

多思考，多考虑优化，逐一对样例，模板题要熟练，容不得半点差错

代码

比赛代码（已改）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n , m;
int s[110];
int v[110][110];
int f[10010];
bool b;
int main(){
	b = true;
	scanf("%d %d" , &n , &m);
	for(int i = 1 ; i <= n ; i++){
		scanf("%d" , &s[i]);
		if(s[i] != 1)
			b = false;
		for(int j = 1 ; j <= s[i] ; j++)
			scanf("%d" , &v[i][j]);
	}
	
	if(b){
		int tmp[110];
		for(int i = 1 ; i <= n ; i++)
			tmp[i] = v[i][1];
		sort(tmp + 1  , tmp + n + 1);
		int sum = 0;
		for(int i = n ; i >= n - m + 1 ; i--)
			sum += tmp[i];
		cout << sum;
		return 0;
	}
	
	if(n == 1){
		int sum[110];
		sum[0] = 0;
		for(int i = 1 ; i <= s[1] ; i++)
			sum[i] = v[1][i] + sum[i - 1];
		int maxn = 0;
		for(int i = 0 ; i <= m ; i++)
			if(maxn < sum[i] + sum[s[1]] - sum[s[1] - m + i])
				maxn = sum[i] + sum[s[1]] - sum[s[1] - m + i];
		cout << maxn;
		return 0;
	}
	//以下WA
//	memset(f , -1 , sizeof(f));
	f[0] = 0;
	int sum[110];
	for(int i = 1 ; i <= n ; i++){
		sum[0] = 0;
		for(int j = 1 ; j <= s[i] ; j++)
			sum[j] = sum[j - 1] + v[i][j];
		
		for(int l = m ; l >= 0 ; l--)//就是这里，当时这重循环放在k循环里面，违反了分组背包的原则，故WA
			for(int j = 0 ; j <= s[i] ; j++) //当前排取j个 
				for(int k = 0 ; k <= j ;  k++)//在当前排的前端取k个 
					if(f[l + j] < f[l] + sum[k] + sum[s[i]] - sum[s[i] - j + k])
						f[l + j] = f[l] + sum[k] + sum[s[i]] - sum[s[i] - j + k];
							
	}
	cout << f[m];
	return 0;
}

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int read(){
	int re = 0 , sig = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-')
			sig = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		re = (re << 1) + (re << 3) + c - '0';
		c = getchar();
	}
	return re * sig;
}

int n , m;
int s , v[110];
int sum[110] , take[110];
int f[10110];
int main(){
	n = read();	m = read();
	for(int  i = 1 ; i <= n ;  i++){
		s = read();
		
		sum[0] = 0;
		for(int j = 1 ; j <= s ; j++)//前缀和
			sum[j] = sum[j - 1] + read();
		
		memset(take , 0 , sizeof(take));
		for(int j = 1 ; j <= s ; j++)//当前排取j个可以获得的最大价值
			for(int k = 0 ; k <= j ; k++){//在当前排的前面取k个（后面取j-k个）
				if(take[j] < sum[k] + sum[s] - sum[s - j + k])
					take[j] = sum[k] + sum[s] - sum[s - j + k];
			}
		
		
		for(int k = m ; k >= 0 ; k--){
			for(int j = 1 ; j <= s ; j++)
				if(f[k + j] < f[k] + take[j])
					f[k + j] = f[k] + take[j];
		}
	}
	cout << f[m];
	return 0;
}