第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;

}