合唱团

题目:有 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);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 慕课网Flask高级编程实战-1.项目准备 和 Flask入门

    如果直接使用/hello 那么不能兼容浏览器不能访问/hello/和/hello,解决办法,路径定义改成/hello/

    Meet相识
  • Scala入门与进阶(二)- Scala入门

    Meet相识
  • Python3入门与实践(一): 基本类型整理

    Meet相识
  • 预处理指令(文件的包含)

    用户1941540
  • Pytest的一些实用技巧

    要注意as出的error并不是实际上抛出的异常,不能使用自定义异常的方法和属性,一般只检查str(error)

    ★忆先★
  • leetcode421. Maximum XOR of Two Numbers in an Array

    Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai< 231.

    眯眯眼的猫头鹰
  • 中国自动驾驶成熟度排名第20,“弱”在技术和基础设施

    近日,四大国际会计事务所之一的毕马威发布了最新报告《自动驾驶汽车成熟度指数》(Autonomous Vehicles Readiness Index,简称“AV...

    镁客网
  • JVM垃圾回收参数说明整理

    启用-server时新生代默认采用并行收集,其他情况下,默认不启用。-server策略为:新生代使用并行清除,年老代使用单线程Mark-Sweep-Compac...

    用户3003813
  • 关于 Dubbo 的重要入门知识点总结

    Dubbo 官网:http://dubbo.apache.org/zh-cn/index.html

    Java技术江湖
  • JVM调优

    -Xmx3550m:设置JVM最大堆内存 为3550M。 -Xms3550m:设置JVM初始堆内存 为3550M。此值可以设置与-Xmx相同,以避免每次垃圾回...

    HUC思梦

扫码关注云+社区

领取腾讯云代金券