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;
}
