目录
牛客_合唱团（打家劫舍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, 且不能小于1
for (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 - d
for(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;
}