有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
输入描述: 每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。
输出描述: 输出一行表示最大的乘积。
输入例子: 3 7 4 7 2 50
输出例子: 49
动态规划：
考虑前i名学生：
F(i,j)
表示前i名学生中选择j个，且最后一个：第i个学生被选中时，正乘积的最大值
H(i,j)
表示前i名学生中选择j个，且最后一个：第i个学生被选中时，负乘积的最小值
例如：4 7 -5 7 则
F(1,1) = 4 ; H(1,1)=0 F(2,1) = 7 ; H(2,1)=0 F(3,1) = 0 ; H(3,1) = -5 F(4,1) = 7 ; H(3,1) = 0
F(2,2) = 28 ; H(2,2) = 0 F(3,2) = 0 ; H(3,2) = -35 F(4,2) = 49; H(4,2) = -35
F(3,3) = 0 ; H(3,3) = -140 F(4,3) = 196 ; H(4,3) = -245
状态转移方程：
if(a[i]>0):
F(i,j)=max⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪a[i]∗F(i−1)(j−1)a[i]∗F(i−2)(j−1)...a[i]∗F(i−d)(j−1)
H(i,j)=max⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪a[i]∗H(i−1)(j−1)a[i]∗H(i−2)(j−1)...a[i]∗H(i−d)(j−1)
if(a[i]<0):
F(i,j)=max⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪a[i]∗H(i−1)(j−1)a[i]∗H(i−2)(j−1)...a[i]∗H(i−d)(j−1)
H(i,j)=max⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪a[i]∗F(i−1)(j−1)a[i]∗F(i−2)(j−1)...a[i]∗F(i−d)(j−1)
则
max(n,k)=max{F(i,k)|0=<i<=n}
#include <iostream>
#include <numeric>
#include<algorithm>
#include <string>
#include<hash_map>
using namespace std;
long long func(
vector<int> vec,
int k,
int d)
{
int n = vec.size();
vector<vector<long long>> MaxPos;
vector<vector<long long>> MinNeg;
MaxPos.resize(n +
1);
MinNeg.resize(n +
1);
for (
auto i =
0; i < MaxPos.size();++i)
{
MaxPos[i].resize(k +
1);
MinNeg[i].resize(k +
1);
}
for (
auto i =
1; i <= n;++i)
{
if (vec[i-
1]>
0)
{
MaxPos[i][
1] = vec[i-
1];
}
if (vec[i-
1]<
0)
{
MinNeg[i][
1] = vec[i-
1];
}
}
long long tmp_maxpos,tmp_minneg;
for (
auto i =
2; i <= n; ++i)
{
for (
auto j =
2; j <= k; ++j)
{
if (i<j)
{
continue;
}
tmp_maxpos =
0;
tmp_minneg =
0;
for (
auto t = i -
1;( t >= i - d && t >
0);--t)
{
if (tmp_maxpos<MaxPos[t][j -
1])
{
tmp_maxpos = MaxPos[t][j -
1];
}
if (tmp_minneg > MinNeg[t][j -
1])
{
tmp_minneg = MinNeg[t][j -
1];
}
}
if (vec[i-
1]>
0)
{
MaxPos[i][j] = tmp_maxpos*vec[i-
1];
MinNeg[i][j] = tmp_minneg*vec[i-
1];
}
if (vec[i-
1]<
0)
{
MaxPos[i][j] = tmp_minneg*vec[i-
1];
MinNeg[i][j] = tmp_maxpos*vec[i-
1];
}
}
}
long long result(
0);
for (
auto i =
0; i < MaxPos.size();++i)
{
if (result<MaxPos[i][k])
{
result = MaxPos[i][k];
}
}
return result;
}
int main()
{
int n, k, d;
vector<int> vec;
#ifdef debug_
n =
7;
vec.push_back(
0);
vec.push_back(
7);
vec.push_back(
4);
vec.push_back(
7);
vec.push_back(-
5);
vec.push_back(
7);
vec.push_back(-
47);
k =
3;
d =
2;
#else
cin >> n;
vec.resize(n);
for (
auto i =
0; i < n;++i)
{
cin >> vec[i];
}
cin >> k >> d;
#endif
cout << func(vec, k, d) << endl;
return 0;
}
