牛客12533题解析：动态规划求解最大乘积问题（附代码实现）

19339201706

一、题目解读

牛客12533题要求从n个人中选择k个人，使他们的能力值乘积最大，且相邻两人编号差不超过d。需考虑正负数的乘积组合情况，通过优化算法找到最优解。

二、解题思路

采用动态规划（Dynamic Programming）解决。定义二维数组dp_max[j]和dp_min[j]，分别表示选j个人且最后一个人为i时的最大和最小乘积。通过状态转移方程，利用前j-1个人的乘积与当前能力值计算，兼顾正×正、负×负、正×负三种情况，避免重复计算。

三、解题步骤

1. 初始化：选1人时，乘积即其能力值。

2. 循环处理选j个人（2≤j≤k），当前人i从j到n遍历。

3. 前一个人l在[i-d, i-1]范围内，计算最大/最小乘积：

○ dp_max[j] = max(dp_max[l][j-1] * ability[i-1], dp_min[l][j-1] * ability[i-1])

○ dp_min[j] = min(dp_max[l][j-1] * ability[i-1], dp_min[l][j-1] * ability[i-1])

4. 最终结果：遍历dp_max[k]（i=k到n）取最大值。

四、代码与注释

1. #include <iostream>
   
2. #include <vector>
   
3. #include <climits>
   
4. using namespace std;
   
5. 
   
6. long long maxProduct(int n, vector<int>& ability, int k, int d) {
   
7.     // dp_max[i][j]表示选j个人，最后一个人是i时的最大乘积
   
8.     // dp_min[i][j]表示选j个人，最后一个人是i时的最小乘积
   
9.     vector<vector<long long>> dp_max(n+1, vector<long long>(k+1, LLONG_MIN));
   
10.     vector<vector<long long>> dp_min(n+1, vector<long long>(k+1, LLONG_MAX));
    
11.    
    
12.     // 初始化：选1个人时就是自己的能力值
    
13.     for(int i = 1; i <= n; i++) {
    
14.         dp_max[i][1] = ability[i-1];
    
15.         dp_min[i][1] = ability[i-1];
    
16.     }
    
17.    
    
18.     for(int j = 2; j <= k; j++) { // 选j个人
    
19.         for(int i = j; i <= n; i++) { // 当前选第i个人
    
20.             // 前一个人只能在[i-d, i-1]范围内
    
21.             int start = max(j-1, i-d); // 至少需要j-1个人
    
22.             for(int l = start; l < i; l++) {
    
23.                 // 考虑三种情况：正×正，负×负，正×负
    
24.                 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]));
    
25.                 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]));
    
26.             }
    
27.         }
    
28.     }
    
29.    
    
30.     // 找出选k个人时的最大乘积
    
31.     long long result = LLONG_MIN;
    
32.     for(int i = k; i <= n; i++) {
    
33.         result = max(result, dp_max[i][k]);
    
34.     }
    
35.     return result;
    
36. }
    
37. 
    
38. int main() {
    
39.     int n, k, d;
    
40.     cin >> n;
    
41.     vector<int> ability(n);
    
42.     for(int i = 0; i < n; i++) cin >> ability[i];
    
43.     cin >> k >> d;
    
44.    
    
45.     cout << maxProduct(n, ability, k, d) << endl;
    
46.     return 0;
    
47. }

复制代码

五、总结

本解法通过动态规划将复杂问题分解为子问题，利用状态转移优化时间复杂度。关键在于处理正负数的乘积逻辑，确保最终结果正确。代码结构清晰，注释明确，适用于同类最大乘积问题的参考与学习。

来源：

牛客网题解