1 题目

图1 合唱团题目

2 解答

是一道动态规划的题目，动态规划有4个关键步骤：

（1）确定状态
（2）确定状态转移方程
（3）赋初始值
（4）判断最终返回值

此题，4个关键步骤的分析如下：

（1）状态表示
假设选定了第j个元素
dpm[i][j] 表示以j为最后元素的学生中选择i个元素的最大能力积(注意此时j是必选)
dpn[i][j] 表示以j为最后元素的学生中选择i个元素的最小能力积(注意此时j是必选)

（2）状态转移方程
即怎么从dp[i-1][j-1]（及以前的元素）得到dp[i][j]
由于前面i-1个人的最大乘积和最小乘积不一定是以j-1结尾，所以我们从允许与j相隔较远的max(1, j-d)开始遍历,
直到j-1,不断更新dpm[i][j]，dpn[i][j],最后得出的dpm[i][j]，dpn[i][j]便是选中i个人，以j结尾的最大、最小乘积。
dpm[i][j]
    = max(max{dpm[i-1][j-d], dpm[i-1][j-d+1]...dpm[i-1][j-2],dpm[i-1][j-1]}*num[j],
               min{dpn[i-1][j-d], dpn[i-1][j-d+1]...dpn[i-1][j-2],dpn[i-1][j-1]}*num[j])

dpn[i][j]
    = min(max{dpm[i-1][j-d], dpm[i-1][j-d+1]...dpm[i-1][j-2],dpm[i-1][j-1]}*num[j],
               min{dpn[i-1][j-d], dpn[i-1][j-d+1]...dpn[i-1][j-2],dpn[i-1][j-1]}*num[j])

（3）初始化
dpm[1][j] = dpn[1][j] = num[j]; 原因：dp[1][j]表示以j为最后元素的学生中选择1个元素的最大能力积，当然就是num[j]了
dpm[i][1] = dpn[i][1] = num[1]; 原因：dp[i][1]表示以1为最后元素的学生中选择i个元素的最大能力积，当然就是num[1]了

（4）返回值
dpm[k][...], dpn[k][...]的最大值

find_max_ability.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include<climits>

using namespace std;

long long FindMaxAbility(vector<int> num, int n, int k, int d)
{
    if (num.size() != n + 1) {
        // 为了符合人的计数习惯，第0个元素空着
        return -1;
    }

    vector<vector<long long>> dpm(k + 1, vector<long long>(n + 1, 0));
    vector<vector<long long>> dpn(k + 1, vector<long long>(n + 1, 0));

    for (int i = 1; i <= k; i++) {
        dpm[i][1] = dpn[i][1] = num[1];
    }
    for (int j = 1; j <=n; j++) {
        dpm[1][j] = dpn[1][j] = num[j];
    }

    for (int i = 2; i <= k;  ++i) {
        for (int j = 2; j <= n; ++j) {
            for (int kk = max(1, j - d); kk < j; ++kk) {
                // 算出dpm[i-1]和dpn[i-1]
                dpm[i][j] = max(dpm[i][j], max(dpm[i-1][kk]*num[j], dpn[i-1][kk]*num[j]));
                dpn[i][j] = min(dpn[i][j], min(dpm[i-1][kk]*num[j], dpn[i-1][kk]*num[j]));
            }
        }
    }

    // 选出最大的乘积
    long long maxAbility = LLONG_MIN;
    for (int i = 1; i <= n; ++i) {
        maxAbility = max(max(maxAbility, dpm[k][i]), dpn[k][i]);
    }
    return maxAbility;
}

int main()
{
    int n;
    cin >> n;

    vector<int> students;
    students.resize(n + 1);
    for(int i = 1; i <= n; ++i) {
        int tmp;
        cin >> tmp;
        students[i] = tmp;
    }

    int k, d;
    cin >> k >> d;

    cout << FindMaxAbility(students, n, k, d) << endl;
    return 0;
}