链接：https://www.nowcoder.com/questionTerminal/661c49118ca241909add3a11c96408c8
来源：牛客网
[编程题]合唱团
- 热度指数：18491 时间限制：1秒 空间限制：32768K
- 算法知识视频讲解
有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
输入描述:
每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 a
i
（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。
输出描述:
输出一行表示最大的乘积。
示例1
输入
3
7 4 7
2 50
输出
49
/*
历程：一开始以为是动态规划，后来觉得不好实现。BFS然后写了半截发现BFS无法实现跳跃，然后看了下50的维度，直接DFS爆搜。果不其然。有20%TLE。 思考DP实现：
暴力DFS时，之所以TLE主要是由于重复计算了大量不需要的值。对于编号i来讲，以i结束，长度为k的乘积mat[i][j]，最大值为a[p]*[j-1]，p<i && p>= i-d.
mat[i][j] =max( mat[p][j-1]*a[i]) p<i && p>= i-d. 需要注意的时a[i]可能<0,所以而且负负得正，我们需要存一个最小矩阵，方程于上类似 matmin[i][j] =min( mat[p][j-1]*a[i],matmin[p][j-1]*a[i])
mat[i][j] = max( mat[p][j-1]*a[i],matmin[p][j-1]*a[i]) p<i && p>= i-d.
*/
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h> using namespace std;
int i,j,k,n,m,d;
int a[];
long long getMax(long long a[],int len){
long long res;
res = a[];
for(i = ;i < len;i++){
if(res < a[i])
res = a[i];
}
return res;
}
long long mat[][];
long long matmin[][];
long long res;
int main()
{
while(cin >> n){
for(i = ; i < n;i++){
cin >> a[i];
}
cin >> k >> d;
memset(mat,,sizeof(mat));
memset(matmin,,sizeof(mat));
for(i = ;i < n;i++){
matmin[i][] = mat[i][] = a[i];
}
int p;
for(i = ;i < n;i++){
for(j = ;j <= k;j++){
long long tmp;
long long tmpmin;
for(p = max(i-d,);p < i;p++){
if(p == max(i-d,)){
tmp = max(mat[p][j-]*a[i],matmin[p][j-]*a[i]);
tmpmin = min(mat[p][j-]*a[i],matmin[p][j-]*a[i]);
}
else{
if(tmp < mat[p][j-]*a[i])
tmp = mat[p][j-]*a[i];
if(tmp < matmin[p][j-]*a[i])
tmp = matmin[p][j-]*a[i]; if(tmpmin > mat[p][j-]*a[i])
tmpmin = mat[p][j-]*a[i];
if(tmpmin > matmin[p][j-]*a[i])
tmpmin = matmin[p][j-]*a[i];
}
}
mat[i][j] = tmp;
matmin[i][j] = tmpmin;
}
}
res = mat[][k];
for(i = ;i < n;i++) if(res < mat[i][k])
res = mat[i][k];
cout << res <<endl;
}
return ;
}