while 1:
    try:
        n = int(raw_input())
        A = map(int, raw_input().split())
        k, d = map(int, raw_input().split())
    except:
        break
    B = [[[0] * 2 for j in range(n)] for i in range(k + 1)]
    for k in range(1, k + 1):
        for i in range(n):
            if k == 1 or i == 0:
                B[k][i][0], B[k][i][1] = A[i], A[i]
            else:
                M = []
                for t in range(1, d + 1):
                    if i - t < 0:
                        break
                    D = B[k - 1][i - t]
                    M.extend([D[0] * A[i], D[1] * A[i]])
                B[k][i][0], B[k][i][1] = min(M), max(M)
    print max([B[k][i][1] for i in range(n)])

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n;
	while (cin >> n){
		vector<int> a(n);
		for (int i = 0; i < n; i++){
			cin >> a[i];
		}
		int k, d;
		cin >> k >> d;
		vector<vector<long long>> dp_max(n, vector<long long>(k + 1, 0));
		vector<vector<long long>> dp_min(n, vector<long long>(k + 1, 0));
		for (int i = 0; i < n; i++){
			dp_max[i][1] = a[i];
			dp_min[i][1] = a[i];
		}
		for (int i = 0; i < n; i++){
			for (int j = 2; j <= k; j++){
				for (int m = max(0, i - d); m <= i - 1; m++){
					dp_max[i][j] = max(dp_max[i][j], max(dp_max[m][j - 1] * a[i], dp_min[m][j - 1] * a[i]));
					dp_min[i][j] = min(dp_min[i][j], min(dp_min[m][j - 1] * a[i], dp_max[m][j - 1] * a[i]));
				}
			}
		}
		long long max_value = dp_max[k - 1][k];
		for (int i = k; i < n; i++){
			max_value = max(max_value, dp_max[i][k]);
		}
		cout << max_value << endl;
	}
	return 0;
}

N = int(raw_input().strip())
ab = map(int, raw_input().strip().split(' '))
(K, D) = map(int, raw_input().strip().split(' '))

dmax = [[0] * N for i in range(K)]
dmin = [[0] * N for i in range(K)]
res = (1 << 64) * -1

for i in range(N):
    dmax[0][i] = dmin[0][i] = ab[i] \
    for k in range(1, K):
        for pre in range(max(0, i - D), i):
            dmax[k][i] = max(dmax[k][i],
                max(dmax[k - 1][pre] * ab[i],dmin[k - 1][pre] * ab[i]))
            dmin[k][i] = min(dmin[k][i],    min(dmax[k - 1][pre] * ab[i], dmin[k - 1][pre] * ab[i]))
    res = max(res, dmax[K - 1][i])

print res

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

int a[55];
ll f[55][15][2];

int main(){
    int n,kk,d;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    scanf("%d%d",&kk,&d);
    ll ans=0;
    for(int i=1;i<=n;i++){
        f[i][1][0]=f[i][1][1]=a[i];
        for(int j=2;j<=kk;++j){
            for(int k=i-1;k>=max(i-d,1);--k){
                f[i][j][0]=max(f[i][j][0],max(f[k][j-1][0]*a[i],f[k][j-1][1]*a[i]));
                f[i][j][1]=min(f[i][j][1],min(f[k][j-1][0]*a[i],f[k][j-1][1]*a[i]));
            }
        }
        ans=max(ans,max(f[i][kk][0],f[i][kk][1]));
    }
    printf("%lld\n",ans);
    return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++){
            nums[i] = scan.nextInt();
        }
        int k = scan.nextInt();
        int d = scan.nextInt();
        long[][] max = new long[k][n];
        long[][] min = new long[k][n];
        for(int i = 0; i < k; i++)
            for(int j = 0; j < n; j++){
            	//min[i][j] = Integer.MAX_VALUE;
            	max[i][j] = 1;
            	if(i == 0){
                    min[i][j] = nums[j];
                    max[i][j] = nums[j];
                }
        }
        
        for(int i = 1; i < k; i++)
            for(int j = 0; j < n; j++)
            	for(int m = 1; m <= d; m++){
            	if(j - m >= 0){
                    if(nums[j] > 0){
            		min[i][j] = Math.min(min[i][j], min[i - 1][j - m] * nums[j]);
            		max[i][j] = Math.max(max[i][j], max[i - 1][j - m] * nums[j]);
                    } else{
                       min[i][j] = Math.min(min[i][j], max[i - 1][j - m] * nums[j]);
                       max[i][j] = Math.max(max[i][j], min[i - 1][j - m] * nums[j]);
                    }
                }
        }
        long Max = 0;
        for(int i = 0; i < n; i++)
            Max = Math.max(Max, max[k - 1][i]);
        System.out.println(Max);

    }
}

1、最大的乘积可能来自之前的最大乘积 * 当前的数值，也有可能来自之前的最小乘积 * 当前的数值，因此使用两个数组maxdp和mindp来记录当前位置处的最大和最小的乘积。
2、maxdp[i][j]表示，在必须以选择第i个同学为结尾的情况下选择j个同学的最大乘积。maxdp[i][j]的值可能来自：
max(maxdp[i-1][j-1]*arr[i], mindp[i-1][j-1]*arr[i])
max(maxdp[i-2][j-1]*arr[i], mindp[i-2][j-1]*arr[i])
...
max(maxdp[i-d][j-1]*arr[i], mindp[i-d][j-1]*arr[i])
选择最大的一个即可。
其中，maxdp[i-?][j-1]表示在i位置之前，以某一位置为结尾时选择j-1个同学的最大乘积，该位置需要满足两个条件：和j的距离不能超过d、该位置之前（包含该位置）必须至少有j-1个同学。
3、mindp与之类似。

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;


long long process(vector<int> array,int n,int k, int d)
{
    vector<long long> tmp(k+1, 0);
    vector<vector<long long>> maxdp(n+1, tmp);
    vector<vector<long long>> mindp(n+1, tmp);
    for(int i=1; i<=n; i++)
    {
        maxdp[i][1] = array[i-1];
        mindp[i][1] = array[i-1];
    }
    for(int i=2; i<=n; i++)
    {
        for(int j=2; j<=k && j<=i; j++)  //总人数不能小于要选择的人数
        {
            long long maxPro = LLONG_MIN;
            long long minPro = LLONG_MAX;
                        //和j的距离不能超过d且该位置之前（包含该位置）必须至少有j-1个同学
            for(int l=max(j-1,i-d); l<=i-1; l++)
            {
                maxPro = max(maxPro, max(maxdp[l][j-1]*array[i-1], mindp[l][j-1]*array[i-1]));
                minPro = min(minPro, min(maxdp[l][j-1]*array[i-1], mindp[l][j-1]*array[i-1]));
            }
            maxdp[i][j] = maxPro;
            mindp[i][j] = minPro;
        }
    }
    long long res = LLONG_MIN;
    for(int i=1; i<=n; i++)
    {
        res = max(res, maxdp[i][k]);
    }
    return res;
}


int main()
{
    int n;
    cin >> n;
    vector<int> array;
    for(int i=0;i<n;i++)
    {
        int tmp;
        cin >> tmp;
        array.push_back(tmp);
    }
    int k,d;
    cin >> k >>d;
    cout << process(array,n,k,d);

    system("pause");
    return 0;
}

#include<stdio.h>
#include<vector>
#include<algorithm>
//#include<windows.h>
using namespace std;
struct node{
	long Max,Min;
	node():Max(0),Min(0){}
};
int a[100];
int main(){
	int N,K,d,i,j,k;
	//freopen("input.txt","r",stdin);
	while(scanf("%d",&N)!=EOF){
		for(i=0;i<N;i++) scanf("%d",&a[i]);
		scanf("%d%d",&K,&d);
		vector<vector<node> > dp(N,vector<node>(K+1));
		long res=-999999999;
		for(i=0;i<N;i++){
			dp[i][1].Max=dp[i][1].Min=a[i];
			res=max(res,dp[i][1].Max);
		}
		for(i=1;i<N;i++)
			for(j=2;j<=min(K,i+1);j++){
				for(k=1;k<=d&&k<=i;k++){
					dp[i][j].Max=max(dp[i][j].Max,max(dp[i-k][j-1].Max*a[i],dp[i-k][j-1].Min*a[i]));
					dp[i][j].Min=min(dp[i][j].Min,min(dp[i-k][j-1].Max*a[i],dp[i-k][j-1].Min*a[i]));
				}
				res=max(res,dp[i][j].Max);
			}
		printf("%ld\n",res);
	}
}

#python2 时间：35ms，内存：3060k 动态规划
length = input()
array = [int(x) for x in raw_input().split()]
k ,d =[int(x) for x in raw_input().split()]
array_max=array_min=array
for i in range(k-1):
    new_max = [-float('inf')]*length
    new_min = [float('inf')]*length
    for num in range(i+1,length):
        index_min = max(i,num-d)
        index_max = min(num+d,length)
        temp_max = -float('inf')
        temp_min = float('inf')
        for temp in range(index_min,num):
            temp_max = max(temp_max,array[num]*array_max[temp],array[num]*array_min[temp])
            temp_min = min(temp_min,array[num]*array_max[temp],array[num]*array_min[temp])
        new_max[num]=temp_max
        new_min[num]=temp_min
    array_max = new_max[:]
    array_min = new_min[:]
print(max(array_max))

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			// 总人数
			int n = sc.nextInt();

			// 学生的能力值，第i个人对应第I个位置
			int[] arr = new int[n + 1];

			// 初始化
			for (int i = 1; i <= n; i++) {
				arr[i] = sc.nextInt();
			}

			// 选择学生数
			int kk = sc.nextInt();

			// 间距
			int dd = sc.nextInt();

			// 规划数组
			long[][] f = new long[n + 1][kk + 1];
			long[][] g = new long[n + 1][kk + 1];

			// 初始化k=1的情况
			for (int one = 1; one < n; one++) {
				f[one][1] = arr[one];
				g[one][1] = arr[one];

			}

			// 总人数等于1 或者大于1
			if (n == 1) {
				System.out.println(arr[1]);
			} else {
				for (int k = 2; k <= kk; k++) {
					for (int one = k; one <= n; one++) {
						long tempmax = Long.MIN_VALUE;
						long tempmin = Long.MAX_VALUE;

						for (int left = Math.max(k - 1, one - dd); left <= one - 1; left++) {
							if (tempmax < Math.max(f[left][k - 1] * arr[one], g[left][k - 1] * arr[one])) {
								tempmax = Math.max(f[left][k - 1] * arr[one], g[left][k - 1] * arr[one]);
							}
							if (tempmin > Math.min(f[left][k - 1] * arr[one], g[left][k - 1] * arr[one])) {
								tempmin = Math.min(f[left][k - 1] * arr[one], g[left][k - 1] * arr[one]);
							}

						}
						f[one][k] = tempmax;
						g[one][k] = tempmin;
					}
				}
				long result = Long.MIN_VALUE;
				for (int one = kk; one <= n; one++) {
					if (result < f[one][kk]) {
						result = f[one][kk];
					}
				}
				System.out.println(result);
			}

		}
	}

} 

比较明了的C++答案

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<long long> a(n+1);
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    int k,d;
    cin>>k>>d;

    vector<vector<long long>> dp_max(n+1,vector<long long>(k+1,0));
    vector<vector<long long>> dp_min(n+1,vector<long long>(k+1,0));

    long long res = LLONG_MIN;
    for(int i=1;i<=n;++i){
        dp_max[i][1] = dp_min[i][1] = a[i];
        for(int j=2;j<=k&&j<=i;++j){
            for(int l=1;l<=d&&i-l>=1;++l){
                dp_max[i][j] = max(dp_max[i][j],max(dp_max[i-l][j-1]*a[i],dp_min[i-l][j-1]*a[i]));
                dp_min[i][j] = min(dp_min[i][j],min(dp_max[i-l][j-1]*a[i],dp_min[i-l][j-1]*a[i]));
            }
        }
        res = max(res,dp_max[i][k]);
    }
    cout<< res<<endl;
}

网易_合唱团解析

1. 题目分析

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

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

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

2. 问题分解

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

从n个学生中，选择k个，可以看成是：先从n个学生里选择最后1个，然后在剩下的里选择k-1个，并且让这1个和前k-1个满足约束条件

2.数学描述

为了能够编程实现，需要归纳出其递推公式，而在写递推公式之前，首先又需要对其进行数学描述

记第k个人的位置为one,则可以用f[one][k]表示从n个人中选择k个的方案。然后，它的子问题，需要从one前面的left个人里面，选择k-1个，这里left表示k-1个人中最后一个（即第k-1个）人的位置，因此，子问题可以表示成f[left][k-1].

学生能力数组记为arr[n+1],第i个学生的能力值为arr[i]
one表示最后一个人，其取值范围为[1,n];
left表示第k-1个人所处的位置，需要和第k个人的位置差不超过d，因此
max{k-1,one-d}<=left<=one-1

在n和k定了之后，需要求解出n个学生选择k个能力值乘积的最大值。因为能力值有正有负，所以

当one对应的学生能力值为正时，
f[one][k] = max{f[left][k-1]arr[i]}(min{k-1,one-d}<=left<=one-1);
当one对应的学生能力值为负时
f[one][k] = max{g[left][k-1]arr[i]}(min{k-1,one-d}<=left<=one-1);
此处g[][]是存储n个选k个能力值乘积的最小值数组

3.编程实现

遍历。因为一般看解答的多半是自己遇到问题不大会的，所以程序里面有写注释。如果大家不懂可以再问我，我回复或者再把解答写详细点。欢迎讨论。

import java.util.Scanner;

public class Main_jrh_AC {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            //总人数
            int n = sc.nextInt();
            //学生能力值数组，第i个人直接对应arr[i]
            int[] arr = new int[n + 1];
            //初始化
            for (int i = 1; i <= n; i++) {//人直接对应坐标
                arr[i] = sc.nextInt();
            }
            //选择的学生数
            int kk = sc.nextInt();
            //间距
            int dd = sc.nextInt();

            /**
             * 递推的时候，以f[one][k]的形式表示
             * 其中：one表示最后一个人的位置，k为包括这个人，一共有k个人
             * 原问题和子问题的关系：f[one][k]=max{f[left][k-1]*arr[one],g[left][k-1]*arr[one]}
             */
            //规划数组
            long[][] f = new long[n + 1][kk + 1];//人直接对应坐标,n和kk都要+1
            long[][] g = new long[n + 1][kk + 1];
            //初始化k=1的情况
            for(int one = 1;one<=n;one++){
                f[one][1] = arr[one];
                g[one][1] = arr[one];
            }
            //自底向上递推
            for(int k=2;k<=kk;k++){
                for(int one = k;one<=n;one++){
                    //求解当one和k定的时候，最大的分割点
                    long tempmax = Long.MIN_VALUE;
                    long tempmin = Long.MAX_VALUE;
                    for(int left = Math.max(k-1,one-dd);left<=one-1;left++){
                        if(tempmax<Math.max(f[left][k-1]*arr[one],g[left][k-1]*arr[one])){
                            tempmax=Math.max(f[left][k-1]*arr[one],g[left][k-1]*arr[one]);
                        }
                        if(tempmin>Math.min(f[left][k-1]*arr[one],g[left][k-1]*arr[one])){
                            tempmin=Math.min(f[left][k-1]*arr[one],g[left][k-1]*arr[one]);
                        }
                    }
                    f[one][k] = tempmax;
                    g[one][k] = tempmin;
                }
            }
            //n选k最大的需要从最后一个最大的位置选
            long result = Long.MIN_VALUE;
            for(int one = kk;one<=n;one++){
                if(result<f[one][kk]){
                    result = f[one][kk];
                }
            }
            System.out.println(result);
        }
    }
}

#include<iostream>
using namespace std;
 
#define MAX 100
inline long long max(long long a,long long b){return a>b?a:b;}
inline long long min(long long a,long long b){return a>b?b:a;}
int main()
{
    int N,K,D;
    int num[MAX]={0};
    long long pMax[MAX][MAX]={0};
    long long pMin[MAX][MAX]={0};
    cin >> N;
    for(int i=1;i<=N;i++)
        cin >> num[i];
    cin>>K>>D;
    //思路造成我的k值在最外循环
    for(int k=1;k<=K;k++)
    {
        for(int i=1;i<=N;i++)
        {
                //思路的差异在初始值上也不同
            if(k==1)
                pMax[k][i]=pMin[k][i]=num[i];
            else
            {
                for(int j=i-1;i-j<=D&&j>0;--j)
                {
                     pMax[k][i]=max(pMax[k][i],max(pMax[k-1][j]*num[i],pMin[k-1][j]*num[i]));
                     pMin[k][i]=min(pMin[k][i],min(pMax[k-1][j]*num[i],pMin[k-1][j]*num[i]));
                }
 
            }
        }
 
    }
    long long result = 0;
    //得出最后的结果
    for(int i=1;i<=N;i++)
        result = max(result,pMax[K][i]);
    cout << result;
    return 0;
}

1. 看到这道题，首先最基本的想法一般是从n中抽取k个数，然后验证是否符合条件，复杂度大概是是一个非指数级可解问题
2. 接着进一步优化，首先可以发现因为限制了相对位置d,所以问题是位置相关的，而根据乘法交换率，计算时位置无关，因此保持其位置而不是考虑排序方法更好归纳问题。因此设人的序列为ListA:a1,a2,....,an
3. 这道题主要超变量有ListA,N.K,D从这道题跟具体的人选取与不选取有关，从头或从尾砍掉或选取一部分人，可以保持这个问题本身性质不变而只在超变量有改变，具有子问题的性质，且是最优化问题且包含最优子问题，因此考虑上贪心算法或者动态规划算法，并且先不考虑正负问题。
4. 贪心的2个要求是最优子问题和贪心选择（在子问题迭代过程每一步都是最佳，其中不会有其它选择优于我的选择【这也是很多贪心算法的证明】）考虑ListA中对an这个人的选择入k和抛弃，前面子问题会变成k-1或者k，显而易见直接丢掉算子问题不能保证最优，因此考虑动态规划。
5. 动态规划要求是最优子问题，重叠子问题，而动态规划又经常被大牛叫为打表算法，因此考虑打表，动态规划首先都要列出递推方程，考虑以砍尾部来划归子问题
6. （图里公式max的第一行d应该为大写D,其应该被重置）
7. 但是这样就会被列为三维矩阵，非常麻烦且不直观，考虑到距离d会因为选择了某人而重置为D所以考虑另外一种切分方法
8. 但是这种方法有个问题就是listA前面的后面可能会空一大截，不一定从尾巴或头部开始切，这也符合实际问题需要。于是表大概就长下面这个样子：
9. 这样就可以解决最大问题了，但是因为涉及正负数，负数最小的可能在下一次乘法中反成最大，所以得考虑打两个表，一个最小表一个最大表，判断哪个大取哪个。
   
10. 照这个思路的具体实现跟高赞答案一样

	
	

		import java.util.Scanner;
//主要参考@菜鸡华的代码
//kk dd one命名引起不适所以替换成简洁有力的命名K D i
//在N的遍历中使其终止与N-K+k，不进行剩下不必要的训练。
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            //读数据
            int N = sc.nextInt();

            int[] arr = new int[N + 1];

            for (int i = 1; i <= N; i++) {
                arr[i] = sc.nextInt();
            }

            int K = sc.nextInt();

            int D = sc.nextInt();

            
            //规划数组表示，使用两个数组保证，最大正数最小负数都有保存
            long[][] f = new long[N + 1][K + 1];//人直接对应坐标,n和K都要+1
            long[][] g = new long[N + 1][K + 1];
            //初始化k=1的情况
            for(int i = 1;i<=N;i++){
                f[i][1] = arr[i];
                g[i][1] = arr[i];
            }
            //自底向上递推
            for(int k=2;k<=K;k++){
                for(int i = k;i<=N-K+k;i++){
                    //求解当i和k定的时候，每步最优子问题   
                    long tempmax = Long.MIN_VALUE;
                    long tempmin = Long.MAX_VALUE;
                    for(int left = Math.max(k-1,i-D);left<=i-1;left++){
                        if(tempmax<Math.max(f[left][k-1]*arr[i],g[left][k-1]*arr[i])){
                            tempmax=Math.max(f[left][k-1]*arr[i],g[left][k-1]*arr[i]);
                        }
                        if(tempmin>Math.min(f[left][k-1]*arr[i],g[left][k-1]*arr[i])){
                            tempmin=Math.min(f[left][k-1]*arr[i],g[left][k-1]*arr[i]);
                        }
                    }
                    f[i][k] = tempmax;
                    g[i][k] = tempmin;
                }
            }
            //从最后一行选取最终最大值
            long result = Long.MIN_VALUE;
            for(int i = K;i<=N;i++){
                if(result<f[i][K]){
                    result = f[i][K];
                }
            }
            System.out.println(result);
        }
    }
} 
	

参考各位大佬的解答如:bupt渣硕,加深自己对动态规划问题的理解,附上代码和理解注释

N = int(raw_input())
A = map(int, raw_input().split())
K, D = map(int, raw_input().split())
#因为有正反所以分成两部分
dpmax = [[0]*N for i in range(K)]#列出未来将要用到的结果位置
dpmin = [[0]*N for i in range(K)]#同上
res = (1<<64)*-1#默认的最小值,后面比较需要
for n in range(N):
    dpmax[0][n] = dpmin[0][n] = A[n]#就是在k=1时，取第一个值时
    for k in range(1,K):
        for pre in range(max(0,n-D),n):#因为有间隔,所以如果间隔大于n,可以全取,反之需从间隔部分之后开始
            dpmax[k][n] = max(dpmax[k][n],max(dpmax[k-1][pre]*A[n],dpmin[k-1][pre]*A[n]))#不断与之前的进行比较获取最大
            dpmin[k][n] = min(dpmin[k][n],min(dpmax[k-1][pre]*A[n],dpmin[k-1][pre]*A[n]))#不断与之前进行比较获取最小
    res = max(res,dpmax[K-1][n])
    #其实结果可以写成max([x for x in dpmax[K-1]]))
    #因为是要在dpmax[K-1]取出最大的那个
print(max([x for x in dpmax[K-1]])))

动态规划问题差不多一次看见,得多找一些练习一下୧(๑•̀⌄•́๑)૭

#include <bits/stdc++.h>

using namespace std;

void search(vector<vector<vector<long>>>& ***, const vector<int>& a, int m_d, int i, int k, int c_d, long product, long& max)
{
    // c_d代表与上一个被选中同学的距离

    if (k == 0)
    {
        if (product > max)
            max = product;
        return;
    }
    // 与上一个同学的距离已经超过了d，不符合要求
    if (c_d >= m_d)
        return;
    if (i >= a.size())
        return;
    // 把剩下所有的同学选了也达不到人数要求，直接跳过
    if (i + k > a.size())
        return;

    // 以下的判断用于缓存数据，减少不必要的判断。不用缓存只能过80％。
    if (abs(product) >= ***[i][k][c_d])
        ***[i][k][c_d] = abs(product);
    else
        return;

    // 选中i
    search(***, a, m_d, i + 1, k - 1, 0, product * a[i], max);

    // 不选中i
    search(***, a, m_d, i + 1, k, product == 1 ? 0 : c_d + 1, product, max);
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int k, d;
    cin >> k >> d;
    vector<vector<vector<long>>> ***(n, vector<vector<long>>(k + 1, vector<long>(d, 0)));
    long max = 0;
    search(***, a, d, 0, k, 0, 1, max);
    cout << max << endl;
}

	思路



	设dpMax = [[1 for i in range(k+1)] for j in range(n+1)]
表示以第i个人为最后一个人，一共选取了j个人时的最大乘积。
同理，dpMin = [[1 for i in range(k+1)] for j in range(n+1)]
表示同样状态下的最小乘积（由于数据中存在负数，负数乘上某个极大的负数反而会变成正的极大值，因而需要同时记录最小值）。
dpMax[i][j] 很显然与dpMax[p][j-1] (for p in range(max(i-d, 0), i)表示遍历当前数之前符合范围条件的所有数， 而 j-1则表示所有数中每一个数对应的只比当前乘积因子数少一个时的结果)相关，可以理解为dpMax[i][j]由两部分组成，一部分是自身作为待选值，另一部分是dpMax[p][j-1]乘上一个人后得到的值，然后取它们的极大值，由此可以得到状态转移方程如下：
dpMax[i][j] = max(dpMax[i][j], max(dpMax[p][j-1]array[i-1], dpMin[p][j-1]array[i-1]))
dpMin[i][j] = min(dpMin[i][j], min(dpMax[p][j-1]array[i-1], dpMin[p][j-1]array[i-1]))

n = int(input())
array = [int(x) for x in input().split()]
k, d =[int(x) for x in input().split()]
dpMax = [[1 for i in range(k+1)] for j in range(n+1)]
dpMin = [[1 for i in range(k+1)] for j in range(n+1)]
result = 0 for i in range(1, n+1): for j in range(1, k+1): for p in range(max(i-d, 0), i):
            dpMax[i][j] = max(dpMax[i][j], max(dpMax[p][j-1]*array[i-1], dpMin[p][j-1]*array[i-1]))
            dpMin[i][j] = min(dpMin[i][j], min(dpMax[p][j-1]*array[i-1], dpMin[p][j-1]*array[i-1])) if dpMax[i][j] > result:
                result = dpMax[i][j] print(result)