题解 | #合唱团#

#include <iostream>
#include <vector>
using namespace std;
struct XPower
{
    XPower()
    {

    }
    //正数
    long long n = 0;
    //负数
    long long f = 0;
};
long long GetMax(vector<int>& power,int n,int k, int d)
{
    vector<vector<XPower>> dp(k,vector<XPower>(n));
    for(int i = 0;i<n;i++)
    {
        if(power[i]>=0)
            dp[0][i].n = power[i];
        else
            dp[0][i].f = power[i];
    }
    for(int i = 1;i<k;i++)
    {
        for(int j = i;j<n;j++)
        {
            for(int l = j-1;l>=0&&j-l<=d;l--)
            {
                if(power[j]>=0)
                {
                    dp[i][j].n = max(dp[i][j].n,dp[i-1][l].n*power[j]);
                    dp[i][j].f = min(dp[i][j].f,dp[i-1][l].f*power[j]);
                }
                else
                {
                    dp[i][j].n = max(dp[i][j].n,dp[i-1][l].f*power[j]);
                    dp[i][j].f = min(dp[i][j].f,dp[i-1][l].n*power[j]);
                }
            }
        }
    }
    long long ans = 0;
    for(int i = 0;i<n;i++)
    {
        ans = max(ans,dp[k-1][i].n);
    }
    return ans;
}
int main() {
    int n;
    while (cin >>n) { // 注意 while 处理多个 case
        vector<int> power(n,0);
        for(int i = 0;i<n;i++)
        {
            cin>>power[i];
        }
        int k,d;
        cin>>k>>d;
        cout<<GetMax(power,n,k,d);
    }
}
// 64 位输出请用 printf("%lld")

思路还是比较简单，动态规划设置dp数组，dp[k][n]，表示在选第k个人时，选到n的最大值（或最小，因为能力值可以为负），注意答案的值比较大，如果使用int会导致溢出，需要使用long long