阿里 7.27笔试题。_要拿出的m个宝物的总价值是各种方案里最大的

题目大概是这样。
有个藏宝架有n层，每层的宝物数量不一，每个宝物都有其价值，现在要求拿出m个宝物，并且需要遵守规则：

每次只能拿选定层的两端的宝物
要拿出的m个宝物的总价值是各种方案里最大的
输入：
n是层数，m是挑选的次数。n<=100,m<=10000
n m
下面每行代表每层，且第一个数是这层宝物的数量k，后面的则是k个宝物的价值 k<=100.
4 1 2 4 5
5 1 2 4 5 5
样例：
2 3
2 3 2
4 1 4 1 5
输出：5+3+2=10

其实这个样例不好，如果直接给
2 2
2 3 2
4 5 5 100 1
输出 1+100= 101
可能就直接知道贪心是求不得最优解的，然后就不会走这么多弯路了。不过就是可能纯粹就是挖坑给你跳吧…
我们这样思考，先求 如果只有一层 5 5 100 1，取2个的最优解是什么？取i个的最优解又是什么？

vector<int> nums = {5,5,100,1};
vector<int> get_i_j(vector<int>&nums){
	int n = nums.size();
	vector<int> presum(n,nums[0]);//前缀和；为了简化计算。
	for(int i=1;i<n;i++) presum[i] += nums[i] + presum[i-1];
	vector<int> value(n,0);
	for(int i=1;i<n;i++){ //求nums选择1，2，3，4个的最优解 
		int min_value = presum[i-1];
		for(int j=0;j<n-i;j++){
			int k = j+i;
			min_value = min(presum[k] - presum[j],min_value); 
			 }
		value[nums.size()-i] = presum[nums.size()-1]-min_value;
		}
	return value;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这样就得到了一层选则，0，1，2，3,j个的最优解放在value中，value[i]表示在nums中选择i个的最优解是多少。
然后可以将每一层的value，放在一个二位的vector<vector> all_values;中，

vector<vector<int>> all_values;
vector<vector<int>> data = {{3,2},{5,5,100,1}};
for (int i=0;i<data.size();i++){
	vector<int> nums = data[i];
	vector<int> tmp(nums.size());
	tmp = get_i_j(nums);  //求每一层的最优解.
	all_values.push_back(tmp);
	}
1
2
3
4
5
6
7
8

然后就可以根据我们定义dp[i][j]，其中i代表到第i层，拿j个的最优解，
所以dp[i][j] = max （dp[i-1][j-x] + all_values[i][x]） x:0-j;
其中x是0到j，表示，i层前面拿 j-x个，i层就拿x个,
即 前面i层拿0个，i层拿j，前面拿1个，i层拿j-1个…中的最大值。
思路大概就是这样了，代码就不写了。