一、问题分析与算法设计

这是一个典型的动态规划问题，需要考虑正负值对乘积的影响。我们需要维护两个DP数组：一个记录最大值，一个记录最小值（因为负负得正）。

二、C++代码实现

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
long long maxProduct(int n, vector<int>& ability, int k, int d) {
// dp_max[i][j]表示选j个人，最后一个人是i时的最大乘积
// dp_min[i][j]表示选j个人，最后一个人是i时的最小乘积
vector<vector<long long>> dp_max(n+1, vector<long long>(k+1, LLONG_MIN));
vector<vector<long long>> dp_min(n+1, vector<long long>(k+1, LLONG_MAX));
// 初始化：选1个人时就是自己的能力值
for(int i = 1; i <= n; i++) {
dp_max[i][1] = ability[i-1];
dp_min[i][1] = ability[i-1];
}
for(int j = 2; j <= k; j++) { // 选j个人
for(int i = j; i <= n; i++) { // 当前选第i个人
// 前一个人只能在[i-d, i-1]范围内
int start = max(j-1, i-d); // 至少需要j-1个人
for(int l = start; l < i; l++) {
// 考虑三种情况：正×正，负×负，正×负
dp_max[i][j] = max(dp_max[i][j],
max(dp_max[l][j-1] * ability[i-1],
dp_min[l][j-1] * ability[i-1]));
dp_min[i][j] = min(dp_min[i][j],
min(dp_max[l][j-1] * ability[i-1],
dp_min[l][j-1] * ability[i-1]));
}
}
}
// 找出选k个人时的最大乘积
long long result = LLONG_MIN;
for(int i = k; i <= n; i++) {
result = max(result, dp_max[i][k]);
}
return result;
}
int main() {
int n, k, d;
cin >> n;
vector<int> ability(n);
for(int i = 0; i < n; i++) cin >> ability[i];
cin >> k >> d;
cout << maxProduct(n, ability, k, d) << endl;
return 0;
}

三、算法解析

1. 数据结构设计：

• 使用两个二维数组分别存储最大值和最小值

• 考虑正负值对乘积的影响

关键处理逻辑：

• 三重循环处理状态转移

• 每次考虑前d个位置的可能情况

• 同时维护最大值和最小值

复杂度分析：

• 时间复杂度：O(nkd)

• 空间复杂度：O(n*k)

来源：牛客网12533，合唱团题解：乘积最大化问题的动态规划解法