https://www.nowcoder.com/practice/661c49118ca241909add3a11c96408c8?tpId=85&tqId=29830&tPage=1&rp=1&ru=/ta/2017test&qru=/ta/2017test/question-ranking

题目描述

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

输入描述:

每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50),表示学生的个数,接下来的一行,包含 n 个整数,按顺序表示每个学生的能力值 a

i

(-50 <= ai <= 50)。接下来的一行包含两个整数,k 和 d (1 <= k <= 10, 1 <= d <= 50)。

输出描述:

输出一行表示最大的乘积。
示例1

输入

复制

3
7 4 7
2 50

输出

复制

49

注意:此题int型会超出范围,要用 long long 
#include<iostream>
#include<stdio.h>
#include<string.h>
#define ll long long
using namespace std;
ll a[];//学生能力值存储数列
ll mx[][],mn[][];//动态数组设为以第i个学生结尾的选取j个人的情况。
int main()
{
int n,k,d;
cin>>n;
for(int i=;i<n;i++)
{
cin>>a[i];
}
cin>>k>>d;
for(int i=;i<n;i++)//初始化
{
mx[i][]=mn[i][]=a[i];
}
for(int i=;i<n;i++)
{
for(int j=;j<k;j++)
{
for(int m=i-;m>=max(,i-d);m--)//因为相邻位置编号差不超过d,所以i-(i-1)<=d,---->i-1>=i-d;
{
mx[i][j]=max(mx[i][j],max(mx[m][j-]*a[i],mn[m][j-]*a[i]));
mn[i][j]=min(mn[i][j],min(mx[m][j-]*a[i],mn[m][j-]*a[i]));//因为能力值有负值,所以负数最小也要考虑
}
}
}
ll ans=mx[][k-];
for(int i=;i<n;i++)
{
ans=max(ans,mx[i][k-]);
}
cout<<ans<<endl;
return ;
}

最新文章

  1. Objective-C快速上手
  2. IAR FOR ARM的安装及破解
  3. android 使用HttpURLConnection方式提交get/post请求
  4. 第05篇. Tomcat和JDK的内存配置
  5. 天气预报接口api(中国天气网)
  6. iOS - VIPER 架构模式
  7. T-SQL openquery 删除报错 “键列信息不足或不正确。更新影响到多行”
  8. iOS开发——Block详解
  9. [week4]每周总结与工作计划
  10. Verdigris: Qt without moc
  11. maven使用.02.一些概念
  12. 使用Maven来创建WEB项目
  13. MyBatis记录
  14. Java 读书笔记 (七) 变量
  15. 关于Oracle配置一些需要注意地方(IIS相关)
  16. tensorflow/core/kernels/conv_ops.cc:659] check failed: stream-&gt;parent()-&gt;getc
  17. Python 21 Django 实用小案例1
  18. 20155326刘美岑 《网络对抗》Exp1 PC平台逆向破解
  19. Struts的JSON机制
  20. C API 连接MySQL及批量插入

热门文章

  1. Spring.Web.Mvc 注入(控制器属性注入)
  2. Ajax——jQuery实现
  3. Shell内置命令
  4. DataTable对象的操作问题
  5. 奇妙的 Storage::url
  6. css总结13:CSS 伪类(Pseudo-classes)
  7. excel中的绝对引用和相对应用
  8. Python Lambda 的简单用法
  9. indexOf(String.indexOf 方法)
  10. laravel中get方式表单提交后, 地址栏数据重复的问题