(动态规划）有 n 个学生站成一排，每个学生有一个能力值，从这 n 个学生中按照顺序选取kk 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 kk 个学生的能力值的乘积最大，返回最大的乘积

第2关：最强战队

挑战任务

绿盟和各大名企合作，举办编程能力大赛，需要选拔一支参赛队伍。队伍成员全部来自“绿盟杯”中表现优秀的同学，每个同学都根据在比赛中的表现被赋予了一个能力值。现在被召集的N个同学已经集结完毕，他们按照编号依次站成了一排。

你需要编写一个程序，从这N个同学中选出S个同学，要求选出的同学的能力值的乘积最大，且要求被选出的相邻两个同学的编号的差不超过D。

编程要求

补全右侧代码区中的getBestTeams(int n,int a[],int kk, int d)函数，实现找出能力值乘积最大而且满足编号要求的同学。将最终结果作为返回值返回，函数参数说明如下：

int n 召集到的同学的人数
int a[] 各个同学的能力值（依次对应不同编号的同学,数组的index就是学生的编号）
int kk 需要选出的同学的人数
int d 相邻同学的编号的差的最大值

测试说明

样例1：
输入：
3 , [7,4,7] , 2 , 50

输出：
49

---

 动态规划，这个是算法里面一直比较难的，当我拿到这个题的时候，有点难以下手，虽然知道要用动态规划但是如何用，自己完全不知道，首先想到找出这个n个数中k个最大的相乘  ，但是很遗憾不对，①要求相邻两个学生之间的编号差不能超过d，②能力值存在负数。
         动态规划是要将问题分解若干子问题，同时子问题之间可能存在包含，我们通常需要保存子问题的结果。
         怎么保存了？数组f[n][m]表示选了n个人方案，最后一的位置为m，那f[n-1][p]就表示选了n-1个人，最后一个位置为p
         怎么分解呢？首先m个人中选n个编号差要求<=d，若已经知道选n-1人的方案，同时这个方案最后一个人的位置为p，我们只需要遍历p+1到p+d的位置求得第n个人的位置。选n个人实际上不知道哪一个作为结尾所以会遍历的求f[n][1]~f[n][m]的最大值
        有负数怎么办？因为有负数所以我们在加一个数组fmin[n][m]表示m个人中选n个间隔为d最小的乘积，最小的也可能成为最大的。
 

#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
#include<limits.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;

int getBestTeams(int n,int a[],int kk,int d){
	long long res=0;
	long long int fmax[11][51]={0};
	long long int fmin[11][51]={0};
	for(int j=1;j<=kk;j++){
		for(int i=1;i<=n;i++){
			if(j==1){
				fmax[j][i]=a[i];
				fmin[j][i]=a[i];
			}
			else{
				for(int p=1;p<=d;p++)
					if(i-p>=1&&i-p<=n){
						fmax[j][i]=max(fmax[j][i],max(fmax[j-1][i-p]*a[i],fmin[j-1][i-p]*a[i]));
						fmin[j][i]=min(fmin[j][i],min(fmax[j-1][i-p]*a[i],fmin[j-1][i-p]*a[i]));
					}			
			}
			res=max(res,fmax[kk][i]);
		}	
	}
	return res;
}


int main(){
	int n,a[51]={0},kk,d;
	while(cin>>n&&n){
		for(int i=1;i<=n;i++)
			cin>>a[i];
		cin>>kk>>d;
		cout<<getBestTeams(n,a,kk,d)<<endl;
	}
	return 0;
}