合唱团

题目：有 n 个学生站成一排，每个学生有一个能力值，从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，返回最大的乘积

image.png

• 解决思路:动态规划

1.抽象状态. 从n个学生中找出k个学生使其编号不超过d并且乘积最大，假设最后一个人的位置为one,则可用f[one][k]来从n个人中表示选出的k个学生位置为one的时候的最大值

f[one][k]（k<=one<=n）(注意这里的k是变化的，不是输入的k)

2.状态转换方程. 要求f[one][k]，只要求出位置为one的前k-1个人的满足条件最大乘积乘以one的能力值就可以了，假设one前面那个人的位置是left，则left应该大于k-1和one-d的较大者，因为left是第k-1个人，他前面至少要有k-2个人，并且他距离one的距离不能超过d；并且left应该小于one-1，因为他是one的前面一个人，则状态转换方程为

f[one][k]=max{f[left][k-1]}*A[one](max(k-1,one-d)<left<one-1)  //求k-1时符合条件的left中的最大值正好满足最优子结构性质

3.扩展. 由于输入条件中能力值可能为负，所以当A[one]为负的时候，他应该是乘以前面k-1个人的最小值，才能使f[one][k]最大，用g[one][k]存储n个人中表示选出的k个学生位置为one的时候的最小值。则状态转换方程应为

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)

4.上面求出了从k到n的每一个f[one][k]，最后只需要找出里面的最大值即可

代码

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);
    }
}