题目:有 n 个学生站成一排,每个学生有一个能力值,从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能力值的乘积最大,返回最大的乘积
image.png
f[one][k](k<=one<=n)(注意这里的k是变化的,不是输入的k)
f[one][k]=max{f[left][k-1]}*A[one](max(k-1,one-d)<left<one-1) //求k-1时符合条件的left中的最大值正好满足最优子结构性质
f[one][k]=max{max{f[left][k-1]}*A[one],min{g[left][k-1]*A[one]})(max(k-1,one-d)<left<one-1)
代码
import java.util.Scanner;
import java.lang.Long;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] A = new int[n+1];
for(int i=1;i<n+1;i++){
//in.next*()方法会阻塞到读取一个了非空格输入
A[i]=in.nextInt();
}
int kk = in.nextInt();
int dd = in.nextInt();
long[][] f = new long[n+1][kk+1]; //f[one][k]存储从n个人中选择满足条件的k个人的乘积最大的
long[][] g = new long[n+1][kk+1]; //f[one][k]存储从n个人中选择满足条件的k个人的乘积最小的
//初始化k为1的情况
for(int one=1;one<n+1;one++){
f[one][1]=A[one];
g[one][1]=A[one];
}
/**动态规划开始,!!!注意这里递归的变量注意是k!!!,one/left是起辅助作用的
f[one][k]=max{f[left][k-1]}*A[one],g[left][k-1]*A[one])(max(k-1,one-d)<left<one-1)
*/
for(int k=2;k<kk+1;k++){ //先确定k
for(int one=k;one<n+1;one++){ //再确定one
long tempMax = Long.MIN_VALUE;
long tempMin = Long.MAX_VALUE;
for(int left=Math.max(k-1,one-dd);left<=one-1;left++){ //然后求k-1时所有满足left的最大值:Math.max(f[left][k-1]*A[one],g[left][k-1]*A[one]),最小值:Math.min(f[left][k-1]*A[one],g[left][k-1]*A[one])
if(Math.max(f[left][k-1]*A[one],g[left][k-1]*A[one])>tempMax)
tempMax = Math.max(f[left][k-1]*A[one],g[left][k-1]*A[one]);
if(Math.min(f[left][k-1]*A[one],g[left][k-1]*A[one])<tempMin)
tempMin = Math.min(f[left][k-1]*A[one],g[left][k-1]*A[one]);
}
//kk之前的最大值最小值都记录下来,这样就递归的求出了f[one][kk],不用再做其他考虑
f[one][k]=tempMax;
g[one][k]=tempMin;
}
}
long result = Long.MIN_VALUE;
for(int one=kk;one<=n;one++){
if(f[one][kk]>result)
result=f[one][kk];
}
System.out.println(result);
}
}