题目描述：
给你一个数列，\(k\)，\(maxDist\)，要你从数列中选出k个数，按照原来的先后顺序排成一个新的数列，要求：新的数列中的每对相邻的数在原数列中的距离不超过\(maxDist\)。求满足条件的数列中，k个元素乘积的最大值。
## 输入 保证数列元素个数不超过\(50\)个。
每个元素在\([-50,50]\)的范围内。
\(k\)在[1,min(10,数列个数)]的范围内。
\(maxDist\)在\([1,50]\)的范围内。
输出
输出最大的乘积
思路：
比较简单的线型动态规划，只要细心些，注意小细节，范围不要搞错剩下的都比较简单。
状态定义
定义\(dp[i][j]\)为取了i个数字，最后一取的数字的位置为j的最大乘积值。
不过这时要注意，由于元素有可能是负数，所以需要从乘积的最小值转移才能达到最大，所以要再开一个数组mn[][]，来记录最小值，其他定义均与dp数组相同
状态转移
转移唯一需要注意的就是范围(其实也可以不注意范围，每次循环完把该清空的地方清空就行了)。
最初把取第一个数的情况赋上(即\(dp(mn)[1][1..n]\)),然后每次的状态从\(dp[j-1][min(1,i-maxDist)......i-1]\)转移得到，至于j的范围，便是\([2,min(k,i)]\).
转移完后最终的答案便是\(max(dp[k][k...n],mn[k][k...n])\)
总体来说还是比较简单的，一般状态好想到的DP都不难。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using namespace std;
typedef long long ll;
int num[N],k,maxDist;
vector<int>numbers;
ll dp[15][N];//取j个,最后一个的位置为k
ll mn[15][N];
void Max(ll &x,ll y){if(x<y)x=y;}
void Min(ll &x,ll y){if(x>y)x=y;}
class TheProduct {
public:
long long maxProduct(vector<int>numbers,int k,int maxDist) {
mms(dp,-63);
mms(mn,63);
ll MIN=dp[0][0],MAX=mn[0][0];
int n=numbers.size();
//预处理
FOR(i,1,n)dp[1][i]=mn[1][i]=numbers[i-1];//取一个数的情况
FOR(i,2,n){
FOR(j,2,min(k,i)){//枚举取数的个数
FOR(l,max(1,i-maxDist),i-1){//枚举上一个数的位置
ll lmx=dp[j-1][l];
ll lmn=mn[j-1][l];
ll num=numbers[i-1];
if(lmx!=MIN)Max(dp[j][i],lmx*num),Min(mn[j][i],lmx*num);
if(lmn!=MAX)Max(dp[j][i],lmn*num),Min(mn[j][i],lmn*num);
//dp为最大值，mn为最小值
}
}
}
ll ans=MIN;
FOR(i,k,n){
if(dp[k][i]!=MIN)Max(ans,dp[k][i]);
if(mn[k][i]!=MAX)Max(ans,mn[k][i]);
//寻找答案
}
return ans;
}
};