题目
有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
输入描述:
每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。
输出描述:
输出一行表示最大的乘积。
example
输入例子:
3
7 4 7
2 50
输出例子:
49
分析
分析：该题目是一个动态规划(Dynamic Programming)的问题，那么我们首先要构造出状态转移方程。不妨设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][k]即可得到最大值。
题解
代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int a[55];
ll maxval[55][15],minval[55][15];
int main(){
int n,k,d;
cin>>n;
for(int i=0;i<n;++i)
cin>>a[i];
cin>>k>>d;
ll res=0;
for(int i=0;i<n;++i){
maxval[i][0]=minval[i][0]=a[i];
}
for(int i=0;i<n;++i){
for(int j=1;j<k;++j){
for(int k;k=i-1;kk>=max(i-d,0);--kk){
maxval[i][j]=max(maxval[i][j],max(maxval[kk][j-1]*a[i],minval[kk][j-1]*a[i]));
minval[i][j]=min(minval[i][j],min(maxval[kk][j-1]*a[i],minval[kk][j-1]*a[i]));
}
}
res=max(res,max(maxval[i][k-1],minval[i][k-1]));
}
cout<<res<<endl;
return 0;
}
second
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int main() {
int N, K, D, i, j, k;
cin >> N;
long long stu[110],fm[110][110], fn[110][110], ans;
ans = 0;
fill(stu, stu + 110, 0);
for (i = 1; i <= N; i++) {
cin >> stu[i];
}
fill(fm[0], fm[0] + 110 * 110, 0);
fill(fn[0], fn[0] + 110 * 110, 0);
cin >> K >> D;
for (i = 1; i <= N; i++) {
fm[i][1] = fn[i][1] = stu[i];
for (k = 2; k <= K; k++) {
for (j = i - 1; j > 0 && i - j <= D; j--) {
fm[i][k] = max(fm[i][k], max(fm[j][k - 1] * stu[i], fn[j][k - 1] * stu[i]));
fn[i][k] = min(fn[i][k], min(fm[j][k - 1] * stu[i], fn[j][k - 1] * stu[i]));
}
}
ans = max(ans, fm[i][K]);
}
cout << ans;
return 0;
}