题解 | #合唱团#

动态规划

思路：

• 考虑以第i(i < n)个元素结尾作为选择的第k(k < K)个值
• 以前d个元素中最大的k-1个元素的乘积来更新当前元素的最大乘积
• 由于(-50 <= ai <= 50)，存在负数，因此当第i个值为负数时，考虑前d个元素的最小值作为更新依据 因此状态转移方程为：

$dpMAX[i][k]=max(dpMAX[i][k],max(dpMAX[j][k-1]\ast arr[i],dpMIN[j][k-1]\ast arr[i]))dpMAX[i][k]\; =\; max(dpMAX[i][k],\; max(dpMAX[j][k-1]*arr[i],\; dpMIN[j][k-1]*arr[i]))$

$dpMIN[i][k]=min(dpMIN[i][k],min(dpMAX[j][k-1]\ast arr[i],dpMIN[j][k-1]\ast arr[i]))dpMIN[i][k]\; =\; min(dpMIN[i][k],\; min(dpMAX[j][k-1]*arr[i],\; dpMIN[j][k-1]*arr[i]))$

最终答案为

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = LLONG_MAX;
const int MINF = LLONG_MIN;

void solve(int n, int K, int d, vector<int>& arr){
    vector<vector<ll>> dpMAX(n,vector<ll>(K+1,0)); // 最大值
    vector<vector<ll>> dpMIN(n,vector<ll>(K+1,0)); // 最小值，由于存在负数，否则直接计算最大值即可
    
    for(int i = 0; i < n; ++i){ // 初始化k=1时，以当前元素结尾的最大最小值
        dpMAX[i][1] = arr[i];
        dpMIN[i][1] = arr[i];
    }
    
    ll ans = MINF;
    
    for(int i = 0; i < n; ++i){
        for(int k = 2; k <= min(i+1,K); ++k){ 
            for(int j = max(0, i-d); j < i; ++j){ // 再坐标差值<=d的范围内更新
                dpMAX[i][k] = max( // 更新最大值
                    dpMAX[i][k], max(dpMAX[j][k-1]*arr[i], dpMIN[j][k-1]*arr[i])
                );
                
                dpMIN[i][k] = min( // 更新最小值
                    dpMIN[i][k], min(dpMAX[j][k-1]*arr[i], dpMIN[j][k-1]*arr[i])
                );
                
            }
        }
        ans = max(ans, dpMAX[i][K]); // 更新结果
    }
    cout<<ans<<endl;
    return;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n,k,d;
    cin>>n;
    vector<int> arr(n);
    for(int i = 0; i < n; ++i){
        cin>>arr[i];
    }
    cin>>k>>d;
    solve(n,k,d,arr);
    return 0;
}