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

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

假设已经确定了k-1个人，那么只要从接下来的d个人中找到使乘积最大的人添加。反过来即得到递推思路，我们以i位置结尾，计算当前的最大乘积dp[i][k]是在j属于i-d到i之间的这部分dp[j][k-1]的基础上考虑的，也就是说一次只考虑d变化。

public class Main{

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int stu[] = new int[N];
        for (int i = 0; i < stu.length; i++) {
            stu[i] = scanner.nextInt();
        }
        int K = scanner.nextInt();
        int D = scanner.nextInt();

        getMaxProduct(N, stu, K, D);
    }

    /**
     * 获取最大乘积
     * 从n个学生中，选择k个，可以看成是：先从n个学生里选择最后1个，然后在剩下的里选择k-1个，并且让这1个和前k-1个满足约束条件
     */
    private static void getMaxProduct(int N, int[] stu, int K, int D) {

        // 记录以当前位置结束的取1-k个值时的最大乘积, 分正负两个情况
        long fmax[][] = new long[N][K];
        long fmin[][] = new long[N][K];

        for (int i = 0; i < N; i++) {
            // 第一个人
            fmax[i][0] = stu[i];
            fmin[i][0] = stu[i];

            // 添加其他人
            for(int k=1; k<K; k++){

                // 每次只考虑添加一个人，那么范围缩小到d了！
                for(int j=i-1; j>=0 && i-j<=D; j--){
                    // 是否替换一定是跟i和问题(乘积)有关的,并且和i-d~i范围的比较
                    fmax[i][k] = Math.max(fmax[i][k], Math.max(fmax[j][k-1]*stu[i], fmin[j][k-1]*stu[i]));
                    fmin[i][k] = Math.min(fmin[i][k], Math.min(fmax[j][k-1]*stu[i], fmin[j][k-1]*stu[i]));
                }
            }
        }

        // 取最小值(负数)只可能存在中间过程，最后结果不管正负都是取最大的那个，所以只在fmax中找
        long max = fmax[0][K-1];
        for (int i = 1; i < N; i++) {
            max = Math.max(max, fmax[i][K-1]);
        }
        System.out.println(max);
    }

}

#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<iostream>
using namespace std;



int main() {
    int n,k,d,temp;
    int maximum=0;
    vector<int> a;
    cin>>n;
    for(int yy=0;yy<n;yy++) {
        cin>>temp;
        a.push_back(temp);
    }
    cin>>k;
    cin>>d;
    int dpm[k][n];
    int dpn[k][n];
    for(int x=0;x<k;x++) {
        for(int y=0;y<n;y++) {
            dpm[x][y]=0;
            dpn[x][y]=0;
        }
    }
    for(int xx=0;xx<n;xx++) {
        dpm[0][xx]=a[xx];
        dpn[0][xx]=a[xx];
    }
    for(int i=0;i<n;i++) {
        for(int kk=1;kk<k;kk++) {
            for(int j=i-1;j>max(-1,i-d-1);j--) {
                dpm[kk][i]=max(dpm[kk][i],max(dpm[kk-1][j]*a[i],dpn[kk-1][j]*a[i]));
                dpn[kk][i]=min(dpn[kk][i],min(dpm[kk-1][j]*a[i],dpn[kk-1][j]*a[i]));
            }
        }
        maximum=max(maximum,dpm[k-1][i]);
    }
    /*for(int xxx=k;xxx<n;xxx++) {
        maximum=max(maximum,dpm[k-1][xxx]);
    }*/
    cout<<maximum<<endl;  
    return 0;
}
这个代码一直卡在50%通过率，
47
-41 -5 -10 -31 -44 -16 -3 -33 -34 -35 -44 -44 -25 -48 -16 -32 -37 
-8 -33 -30 -6 -18 -26 -37 -40 -30 -50 -32 -5 -41 -32 -12 -33 -22 -14 -34
 -1 -41 -45 -8 -39 -27 -23 -45 -10 -50 -34 
6 3
这个例子上，正确的输出应该是5504557500

我的输出为:

2135936000

/*背包变形 + 状态压缩*/
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char *argv[])
{
    long dp[50][2], res;
    int a[50], n, k, d, i, j, delta;
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
    {
        scanf("%d", a + i);
        dp[i][0] = dp[i][1] = a[i];
    }
    scanf("%d%d", &k, &d);
    for (i = 1; i < k; ++i)
    {
        for (j = n - 1; j >= i; --j)
        {
            for (delta = 1; delta <= d && j >= delta; ++delta)
            {
                dp[j][0] = min(dp[j][0], min(dp[j - delta][0] * a[j], dp[j - delta][1] * a[j]));
                dp[j][1] = max(dp[j][1], max(dp[j - delta][0] * a[j], dp[j - delta][1] * a[j]));
            }
        }
    }
    for (res = dp[k - 1][1], i = k; i < n; ++i)
    {
        if (dp[i][1] > res)
        {
            res = dp[i][1];
        }
    }
    printf("%ld\n", res);
    return 0;
}