网易编程题(合唱团)_njudongchen的博客-程序员宅基地

技术标签: 编程  编程练习  网易  

网易编程题(合唱团)

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

输入描述:
每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50),表示学生的个数,接下来的一行,包含 n 个整数,按顺序表示每个学生的能力值 ai(-50 <= ai <= 50)。接下来的一行包含两个整数,k 和 d (1 <= k <= 10, 1 <= d <= 50)。

输出描述:
输出一行表示最大的乘积。

输入例子:
3
7 4 7
2 50

输出例子:
49

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int  main()
{

    long long temp_k = -1e17;
    vector< long long > students;
    long long  n;
    cin >> n;
    long long  sum = n;
    while (n--)
    {
        long long  temp;
        cin >> temp;
        students.push_back(temp);
    }
    long long  k, d;
    cin >> k >> d;

    struct min_max{
        min_max() :min{ 0 }, max{ 0 }{};
        long long min;
        long long max;
    };
    //声明结构体,因为有正有负所以要保存最大值和最小值
    //vector<vector< long long >> *res = new vector<vector< long long >>{ n, vector< long long >{d, 0} };
    vector<vector<min_max>> *res = 
            new vector<vector< min_max>>(sum, vector<min_max>(k, min_max()));
    for (long long i = 0; i <sum; ++i)
    {
        (*res)[i][0].max = (*res)[i][0].min = students[i];
    }
    //以i结尾的至多包含k个数字的成绩的最大值和最小值;
    for (long long i = 1; i <sum; ++i)
    {
        for (long long j = 1; j <= i&&j < k; ++j)
        {
            long long temp_min = -1e17;
            long long temp_max = 1e17;
            for (long long w = 1; w<i + 1 && w <= d; ++w){
                if (temp_min<max(students[i] * (*res)[i - w][j - 1].min, 
                                students[i] * (*res)[i - w][j - 1].max))
                    temp_min = max(students[i] * (*res)[i - w][j - 1].min, 
                                students[i] * (*res)[i - w][j - 1].max);
                if (temp_max>min(students[i] * (*res)[i - w][j - 1].min, 
                                students[i] * (*res)[i - w][j - 1].max))
                    temp_max = min(students[i] * (*res)[i - w][j - 1].min, 
                                students[i] * (*res)[i - w][j - 1].max);
            }
            (*res)[i][j].max = temp_min;
            (*res)[i][j].min = temp_max;
        }
    }
    for (auto c : (*res))
    {
        if (c[k - 1].max>temp_k)
            temp_k = c[k - 1].max;
    }
    cout << temp_k << endl;
    delete res;
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/njudongchen/article/details/54924362

智能推荐

scss值列表_Sass中的数据类型_weixin_40003512的博客-程序员宅基地

数据类型几乎在所有编程语言当中都有,在Sass中也不例外。数据类型是根据不同的用途分的类。例如2是一个数值(number),而SitePoint是一个字符串(string)。在这篇文章中,将涵盖Sass中所有的数据类型(共有七种数据类型),并且通过一些简单的例子来阐述这些数据类型在Sass中如何使用。Nullnull是Sass中最基本的数据类型,它既不是true也不是false,而表示的是空。它没...

win10安装opcenum_U盘安装WIN10时显示 windows无法安装到这个磁盘 选中的磁盘采用GPT分区形式..._CRomputer-罗军的博客-程序员宅基地

一、原因分析win8/win10系统均添加快速启动功能,预装的win8/win10电脑默认都是UEFI引导和GPT硬盘,传统的引导方式为Legacy引导和MBR硬盘,UEFI必须跟GPT对应,同理Legacy必须跟MBR对应。如果BIOS开启UEFI,而硬盘分区表格式为MBR则无法安装;BIOS关闭UEFI而硬盘分区表格式为GPT也是无法安装Windows。(注意事项:转换分区表格式会清空硬盘所有...

Unity 在Game窗口下显示mesh_皮皮#2500的博客-程序员宅基地_unity 显示mesh

Unity 在Game窗口下显示mesh问题描述实现方法问题描述在Scene窗口中,当我们点击一个物体时,会显示出一个物体的纹理:但是在Game窗口中,我们时看不到这个纹理的:目标:希望在Game窗口中可以看到和Scene窗口中一样的纹理效果。实现方法安装插件Wireframe将解压后的工程放到Unity工程Asset文件夹下:在Unity中,新建一个材质球,然后将Wireframe文件夹下的UCLA GameLab Wireframe.sh着色器附加到新建的材质球上:将材质球附加

mui:第一次在AppStore 上线应用_前行中632的博客-程序员宅基地

时间:在第一天上午发布,第二天早上便通过了,所以整体还是很快的 过程:整体是一个开发了差不多有两个月的项目—易沃克,从最初的一无所知的忐忑,到最后的淡然,感觉受益良多,(闲话少说) 这是H5的项目,是基于mui框架的基本模型,总体上是有js和html语言写成,并已经实现了具体的功能,可以投入使用,但作为一个H5文件,不可避免的就是他的性能瓶颈,他的刷新可以说是令人很不满意的,我使用的是appup

关于Redis远程连接Linux虚拟机(Centos 7)或IDEA的问题_老码的博客-程序员宅基地

关于Redis远程连接Linux虚拟机(Centos 7)或IDEA的问题今天在学习Redis中遇到了一点小问题:使用Xshell远程连接虚拟机时,无法成功连接,需要切换到桥接模式使用IDEA远程连接,与SpringBoot项目集成时,无法Ping通,无法成功连接由于桥接模式下ip地址每次启动虚拟机都会不同,也就意味着需要在Xshell中多次配置连接的ip,所以一般我们都选择通过Nat连接。但是虚拟机设置了通过Nat连接后,我发现不能成功连接到Xshell,所以需要以下设置:首先进入Red

查找IIS的80端口被占方法_SKY徐的博客-程序员宅基地

运行cmd,键入netstat -ano,找到80端口,查看其对应的PID为720, 然后打开任务管理器,点击查看-选择列,勾上PID,确定,以显示进程的PID信息,然后打开进程去找对应的PID为720的进程,这个进程就是占用80端口的进程,结束掉即可运行你的IIS了,或是想办法把端口改了,或是改IIS的也行,

随便推点

Hibernate注释大全_zhugeyangyang1994的博客-程序员宅基地

每个持久化POJO类都是一个实体Bean, 通过在类的定义中使用@Entity 注解来进行声明。声明实体[email protected] class Flight implements Serializable {  Long id;  @Id  public Long getId() { return id; }  public void setId(Long

html避免多次点击选中页面文字或者内容时出现蓝色背景_chengchengbox的博客-程序员宅基地

在body、html中添加以下代码*,body,html{ -moz-user-select: none; /*火狐*//*选中文字时避免出现蓝色背景*/ -webkit-user-select: none; /*webkit浏览器*//*选中文字时避免出现蓝色背景*/ -ms-user-select: none; /*IE10*//*选中文字时避免出现蓝色背景*/ user-select: none;/*选中文字时避免出现蓝色背景*/}...

PHP拼团人数不能超过,怎么解决拼团、抽奖难以凑齐人数这个大问题?_weixin_39552472的博客-程序员宅基地

原标题:怎么解决拼团、抽奖难以凑齐人数这个大问题? 相信大家都参与过小程序组团、互动类的活动,通常是要等到人数达到规定人数后,活动才能够开始进行。在发起人发起了一个小程序拼团活动、抽奖活动……转发给多个微信好友后,再等待人数集齐,但是,并不是所有好友都会第一时间加入活动,这就需要反复点击查看人数参与进度,以便活动开始。 然而,不断地点击查看人数会消磨掉用户的热情和耐心,用户也会在等待中遗忘或是直接...

Sql 语句中执行 定义变量的SQL语句_Jimmy_Cheung的博客-程序员宅基地

第一:定义 @strsql SET @strsql='                INSERT INTO SEOrder            (FExSeorderNo,FExSeorderVal,FInterID,FBillNo,FBrNo,FTranType,FCancellation,FStatus,FDiscountType,Fdate,         

Android VLC 播放器_af3073496391的博客-程序员宅基地

VLC转载于:https://www.cnblogs.com/fgjTarget/p/3718342.html

小白的项目开发经历(持续开发中...)_晓晶的博客-程序员宅基地_开发 项目经历

文章目录一、前言二、项目列表1. 实时车流监控及精准停车服务系统2.读入数据总结一、前言整理下之前的个人项目开发经历,也算是对自己的程序员生涯进行了一次总结,校园内开发的项目还是很稚嫩,但真的是一步一步通宵摸爬滚打出来的作品(然鹅现在仍然还是一个小白),希望在以后能够继续开发出更好的项目呀,笔芯~~二、项目列表1. 实时车流监控及精准停车服务系统bilibili视频:https://www.bilibili.com/video/BV1c54y1a7jV/git地址:项目太久远,源码missin