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

fiwhgikbl

一、问题分析与算法设计

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

二、C++代码实现

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],
    
25.                                   max(dp_max[l][j-1] * ability[i-1],
    
26.                                      dp_min[l][j-1] * ability[i-1]));
    
27.                 dp_min[i][j] = min(dp_min[i][j],
    
28.                                   min(dp_max[l][j-1] * ability[i-1],
    
29.                                      dp_min[l][j-1] * ability[i-1]));
    
30.             }
    
31.         }
    
32.     }
    
33.    
    
34.     // 找出选k个人时的**乘积
    
35.     long long result = LLONG_MIN;
    
36.     for(int i = k; i <= n; i++) {
    
37.         result = max(result, dp_max[i][k]);
    
38.     }
    
39.     return result;
    
40. }
    
41. 
    
42. int main() {
    
43.     int n, k, d;
    
44.     cin >> n;
    
45.     vector<int> ability(n);
    
46.     for(int i = 0; i < n; i++) cin >> ability[i];
    
47.     cin >> k >> d;
    
48.    
    
49.     cout << maxProduct(n, ability, k, d) << endl;
    
50.     return 0;
    
51. }

复制代码

三、算法解析

• 数据结构设计：
  
  
  • 使用两个二维数组分别存储**值和最小值
  • 考虑正负值对乘积的影响
    
    
• 关键处理逻辑：
  
  
  • 三重循环处理状态转移
  • 每次考虑前d个位置的可能情况
  • 同时维护**值和最小值
    
    
• 复杂度分析：
  
  
  • 时间复杂度：O(nkd)
  • 空间复杂度：O(n*k)
    
    

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