题目描述
有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
输入描述:
每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。
输出描述:
输出一行表示最大的乘积。
示例1
输入
3 7 4 7 2 50
输出
49
1 //最优解一般可以考虑动态规划。针对这题，可以先在第i个位置找到最后一个人k,记为f[k][i].那么 2 //前一个人即第k-1个人可以在位置j上找到。那么可以记为f[k-1][j].其中i,j相差值要小于等于d，即 i-d=<j<=i-1 3 //同时要注意，最大的乘积有两种情况：1是当前该位置a[i]为正数，那么应该选子问题最大乘积值乘以这个数。2如果当前位置a[i]为负数，反而要选取子问题 4 //最小的乘积值。所以可以用两个二维数组fmax[i][j]和fmin[i][j]来维护子问题的最值。其中0=<i<=k 0=<j<=n 5 #include<iostream> 6 #include<math.h> 7 #include<vector> 8 #include<limits.h> 9 #include<algorithm> 10 using namespace std; 11 long long max(long long a,long long b) 12 { 13 return a>b?a:b; 14 } 15 long long min(long long a,long long b) 16 { 17 return a<b?a:b; 18 } 19 int main() 20 { 21 int n; 22 cin>>n; 23 vector<long long> a(51); 24 long long temp; 25 for(int i=1;i<=n;i++){ 26 cin>>temp; 27 a[i]=temp; 28 } 29 int k,d; 30 cin>>k>>d; 31 long long fmax[51][51]; 32 long long fmin[51][51]; 33 int i,j,kk; 34 long long res=~0LL; 35 for(i=1;i<=n;i++) 36 { 37 fmax[1][i]=a[i]; 38 fmin[1][i]=a[i]; 39 for(kk=2;kk<=k;kk++){ 40 for(j=i-1;j>0&&i-j<=d;j--){ 41 fmax[kk][i]=max(fmax[kk][i],max(fmax[kk-1][j]*a[i],fmin[kk-1][j]*a[i])); 42 fmin[kk][i]=min(fmin[kk][i],min(fmin[kk-1][j]*a[i],fmax[kk-1][j]*a[i])); 43 } 44 } 45 res=max(res,fmax[k][i]); 46 } 47 cout<<res; 48 return 0; 49 }