每日OJ_牛客_合唱团（打家劫舍dp）

牛客_合唱团（打家劫舍dp）

解析代码1

解析代码2

牛客_合唱团（打家劫舍dp）

合唱团__牛客网

有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？

解析代码1

题目解析：题目要求n各学生中选择k个，使这k个学生的能力值乘积最大。这是一个最优化的问题。另外，在优化过程中，提出了相邻两个学生的位置编号差不超过d的约束。解决的方法是采用动态规划。

代码分析：该题目是一个动态规划的问题，那么我们首先要构造出状态转移方程。设maxVal[i][j]表示以第i个人为最后一个（前面共i个人，最后一个人必选），一共选取了j个人（包含i）时的最大乘积。同理，minVal[i][j]表示同样状态下的最小乘积（由于数据中存在负数，负数乘上某个极大的负数反而会变成正的极大值，因而需要同时记录最小值）。 maxVal[i][j]很显然与maxVal[i][j-1]相关，可以理解为maxVal[i][j]由两部分组成，一部分是自身作为待选值，另一部分是maxVal[i][j-1]加上一个人后得到的值，然后取它们的极大值，由此可以得到状态转移方程如下：

maxVal[i][j] = max(maxVal[i][j], max(maxVal[c][j - 1] * a[i], minVal[c][j - 1] * a[i])); minVal[i][j] = min(minVal[i][j], min(maxVal[c][j - 1] * a[i], minVal[c][j - 1] * a[i])); 其中c的约束条件： i - d <= c <= i - 1 初始状态： maxVal[i][1] = a[i]; 最后遍历Maxval[i][k]即可得到最大值。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// 数据类型必须是long long类型，不然会溢出
long long getMax(vector<int>& v, int n, int k, int d)
{// 状态F(i,j)： 以第i个人为最后一个人，总共选了j个人的最大值vector<vector<long long>> maxValue(n + 1, vector<long long>(k + 1, 0));vector<vector<long long>> minValue(n + 1, vector<long long>(k + 1, 0));// 初始化F(i, 1): 以第i个人为最后一个人，共选了1个人的最大值long long ret = 0;for (int i = 1; i <= n; ++i){maxValue[i][1] = minValue[i][1] = v[i - 1];}for (int i = 1; i <= n; ++i){// 需要选取k个人for (int j = 2; j <= k; ++j){// 约束条件：i - d <= m <= i - 1, 且不能小于1for (int m = i - 1; m >= max(i - d, 1); --m){maxValue[i][j] = max(maxValue[i][j], max(maxValue[m][j - 1] * v[i - 1],minValue[m][j - 1] * v[i - 1]));minValue[i][j] = min(minValue[i][j], min(maxValue[m][j - 1] * v[i - 1],minValue[m][j - 1] * v[i - 1]));}}// 更新最大值ret = max(ret, maxValue[i][k]);}return ret;
}int main()
{int n, k, d;cin >> n;vector<int> v(n, 0);for (int i = 0; i < n; ++i){cin >> v[i];}cin >> k;cin >> d;cout << getMax(v, n, k, d);return 0;
}

解析代码2

打家劫舍dp

#include <iostream>
#include <queue> // 里面有vector
#include <vector>
using namespace std;#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;signed main()
{int n = 0, k = 0, d = 0;cin >> n;vector<int> arr(n + 1);for(int i = 1; i <= n; ++i){cin >> arr[i]; // 还有负值}cin >> k >> d;vector<vector<int>> f(n + 1, vector<int>(k + 1, -INF));vector<vector<int>> g(n + 1, vector<int>(k + 1, INF));// f[i][j]/g[i][j]表示从1到i挑选j个人第i个人必选的最大/小乘积for(int i = 1; i <= n; ++i){f[i][1] = g[i][1] = arr[i]; // 初始化for(int j = 2; j <= min(i, k); ++j){// i - prev <= d 所以 prev >= i - dfor(int prev = max(i - d, j - 1); prev <= i - 1; ++prev) // prev代表前面挑选的最后一个位置{f[i][j] = max(f[i][j], max(f[prev][j - 1] * arr[i], g[prev][j - 1] * arr[i]));g[i][j] = min(g[i][j], min(f[prev][j - 1] * arr[i], g[prev][j - 1] * arr[i]));}}}int res = 0;for(int i = k; i <= n; ++i){res = max(res, f[i][k]);}cout << res << endl;return 0;
}