合唱团

题目描述

有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？

输入描述:

每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。

输出描述:

输出一行表示最大的乘积。 示例1

输入

3 7 4 7 2 50

输出

49

1. 题目分析

题目要求n各学生中选择k个，使这k个学生的能力值乘积最大。这是一个最优化的问题。另外，在优化过程中，提出了相邻两个学生的位置编号差不超过d的约束。

如果不用递归或者动态规划，问题很难入手，并且，限制条件d也需要对每一个进行约束，编程十分复杂

所以，解决的方法是采用动态规划（理由：1.求解的是最优化问题；2.可以分解为最优子结构）

2. 问题分解

1.对该问题的分解是关键。

定义fm[k][i]表示当选中了k个学生，并且以第i个学生为结尾，所产生的最大乘积；

fn[k][i]表示 当选中了k个学生，并且以第i个学生为结尾，所产生的最小乘积；

因为有正有负，负负得正，所以要维护两个dp数组，一个存储最大，一个存储最小。

那么fm[k+1][i+1]=max(fm[k][i]*stu[i+1],fn[k][i]*stu[i+1])，即当选中了k个学生后，再选择第i+1编号学生，所产生的最大乘积； 然而，并不能保证上一次选择的就是第i个学生，所以要遍历子数组fm[k]，令j从i到1，并且j与i+1之间小于间隔D， 遍历fm[k][j]，以及fn[k][j]； 同理fn[k+1][i+1]=min(fn[k][i]*stu[i+1],fm[k][i]*stu[i+1])。 最后，遍历一遍fm[K][i]求得最大值（i从1～N）。