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

20小时前牛客题解30

一、问题分析与算法设计

这是一个典型的动态规划问题，需要考虑正负值对乘积的影响。我们需要维护两个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;
}