牛客对应题目链接：合唱团_牛客题霸_牛客网 (nowcoder.com)
一、分析题目
线性 dp。
1、状态表示
f[i][j]：从前 i 个人中挑选出 j 个人，arr[i] 必选的最大乘积。
g[i][j]：从前 i 个人中挑选出 j 个人，arr[i] 必选的最小乘积。
2、返回值
返回 max(f[k][k] ~ f[n][k])。
3、状态转移方程
f[i][j] = max(f[prev][j-1] * arr[i], g[prev][j-1] * arr[i]);（max(i-d, j-1) <= prev <= i-1）
f[i][j] = min(f[prev][j-1] * arr[i], g[prev][j-1] * arr[i]);（max(i-d, j-1) <= prev <= i-1）
4、初始化
- f[i][j]=-INF，g[i][j]=INF（避免影响后续取值）
- f[i][1] = g[i][1] = arr[i]
注意：这里的取值范围很大，所以要用到 long long 来存储结果，那么这里的 INF 可以设为 LLONG_MAX 或 0x3f3f3f3f3f3f3f3f。
二、代码
//值得学习的代码 #include <iostream> using namespace std; typedef long long LL; const int N = 55, M = 15; const LL INF = 0x3f3f3f3f3f3f3f3f; int n, k, d; LL arr[N]; LL f[N][M], g[N][M]; int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> arr[i]; cin >> k >> d; // 初始化放在填表中进⾏了 for(int i = 1; i <= n; i++) // 填写每⼀⾏ { g[i][1] = f[i][1] = arr[i]; for(int j = 2; j <= min(i, k); j++) // 挑选⼏个⼈ { f[i][j] = -INF; // 初始化 g[i][j] = INF; // 初始化 for(int prev = max(i - d, j - 1); prev <= i - 1; prev++) // 前⾯挑选的最后⼀个位置 { f[i][j] = max(max(f[prev][j - 1] * arr[i], g[prev][j - 1] * arr[i]), f[i][j]); g[i][j] = min(min(f[prev][j - 1] * arr[i], g[prev][j - 1] * arr[i]), g[i][j]); } } } LL ret = -INF; for(int i = k; i <= n; i++) ret = max(ret, f[i][k]); cout << ret << endl; return 0; }
三、反思与改进
这题真没有思路，加上前面的题目也没有通过全部样例，有点影响对这道题的思考。认真反思，汲取经验。
