首页 > 每日一题 -- 11-1

每日一题 -- 11-1

一天十题选择，一天一道编程，一天一个面试题，一个一个剑指offer

排序是必须要掌握的一个算法，非常的重要

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

3

7 4 7

2 50

输出

49

题目分析

本题是网易的一道动态规划的题目，题目中让我们求解的是一个最优解的问题，我们这里可以考虑使用的算法是动态规划来进行求解，这里我们需要求解从n个人当中选择k使得这k的乘积最大，这个问题我们就需要设置的 二维数组，数组的中表示的是第i个数作第j个乘数的时候的最大值，这里我们需要维护一个最大值的数组，还需要维护一个最小值的数组，原因是，我们的最大值可能是由我们的最小值的一个负数乘以一个负数得到的，同时我们的最小值也可能是最大值中的一个最大数乘以我们的一个负数得到的，所以这里需要维护两个数组，同时还应该注意的一个问题就是，我们的数据中，还需要控制的一个间距。

代码

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
using namespace std;int main()
{int n;while (cin >> n){vector<long long> arr(n);for (int i = 0; icin >> arr[i];}int k, d;cin >> k >> d;vector<vector<long long>> dp_max(n, vector<long long>(k + 1, 0));vector<vector<long long>> dp_min(n, vector<long long>(k + 1, 0));//初始化最大和最小数组for (int i = 0; i1] = arr[i];dp_min[i][1] = arr[i];}for (int i = 0; ifor (int j = 2; j1; j++){for (int m = max(0, i - d); m<=i - 1; m++) //这里的m控制的是间隔，就是说，我们的间隔要控制好了{dp_max[i][j] = max(dp_max[i][j], max(dp_max[m][j - 1] * arr[i], dp_min[m][j - 1] * arr[i]));dp_min[i][j] = min(dp_min[i][j], min(dp_min[m][j - 1] * arr[i], dp_max[m][j - 1] * arr[i]));}}}long long maxnum = dp_max[k-1][k];for (int i = k; icout << maxnum << endl;}return 0;
}

更多相关：

  • 傅里叶变换之看不懂就掐死我教程

    原文出处： 韩昊    1 2 3 4 5 6 7 8 9 10 作 者：韩 昊 知 乎：Heinrich 微 博：@花生油工人 知乎专栏：与时间无关的故事   谨以此文献给大连海事大学的吴楠老师，柳晓鸣老师，王新年老师以及张晶泊老师。   转载的同学请保留上面这句话，谢谢。如果还能保留文章来源就更感激不尽了。 我保证这篇文章...

  • 深入浅出的讲解傅里叶变换（完整）

    原文出处： 韩昊   我保证这篇文章和你以前看过的所有文章都不同，这是 2012 年还在果壳的时候写的，但是当时没有来得及写完就出国了……于是拖了两年，嗯，我是拖延症患者…… 这篇文章的核心思想就是： 要让读者在不看任何数学公式的情况下理解傅里叶分析。 傅里叶分析不仅仅是一个数学工具，更是一种可以彻底颠覆一个人以前世界观的思维...

  • Ubuntu 12.04下玩转终端管理器Byobu

    很多Linux高手都喜欢使用screen命令，screen命令可以使你轻松地使用一个终端控制其他终端。尽管screen本身是一个非常有用的工具，byobu作为screen的增强版本，比screen更加好用而且美观，并且提供有用的信息和快捷的热键。 想象一下这样一个场景：你通过Secure Shell(ssh)链接到一个服务器，并...

  • NBIOT-NPSS/NSS/NPBCH的资源位置

    NarrowbandPrimary Synchronization Signal时域位置每1个SFN存在一个NPSSSFNSubframeSymbol长度每个SFN5最后11个symbol11个symbols频域位置NB-IOT下行带宽固定180kHz，一个PRB，12个子载波。...

  • shell中引号的使用方法

     [h1]反斜杠只能够阻止一个字符  [h2]位于键盘的左上角，和~公用一个键。...

  • 剑指offer：面试题19. 正则表达式匹配

    题目：正则表达式匹配 请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。 示例 1:...

  • BZOJ 1801 [Ahoi2009]中国象棋（线性动规）（洛谷P2051）

    题意：就是在n*m的格子中放“炮”（中国象棋中的棋子）问有多少种放法，使得没有任意的两个炮相互攻击 思路：我们很容易的得到一列或者一行中最多放下两个炮（我也只能得到这些了，满脑子状压，但数据范围有100），这篇博客些的很好（传送门），我们定义dp[i][j][k]代表前i行我们有j列式有2个棋子，有k列是一个棋子，那么我们空的列的个数...

  • 【洛谷习题】小A点菜

    虽然也是一道dp的入门题，但就是想不到，或者说不会实现。dp还是要多做题。 链接：https://www.luogu.org/problemnew/show/P1164   我们可以设dp[i][j]表示以考虑完第i件，恰好消费j元的方案数。那么dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]]，也就是讨论第i件点...

  • 【题解】 bzoj1260: [CQOI2007]涂色paint （区间dp）

    bzoj1260，懒得复制，戳我戳我 Solution: 这种题目我不会做qwq，太菜了区间打牌(dp) 用f[l][r]表示从l到r最少需要染几次色。状态转移方程： 1.(f[l][r]=min(f[l][i],f[i+1][r]) (l<=i

  • 模拟城市2.0

    题目背景 博弈正在机房颓一个叫做《模拟城市2.0》的游戏。 2048年，经过不懈努力，博弈终于被组织委以重任，成为D市市委书记！他勤学好问，励精图治，很快把D市建设成富强民主文明和谐的美好城市。为了进一步深化发展，他决定在海边建立一个经济开发区。 题目描述 已知开发区的建筑地块是一个n×nn imes nn×n的矩形，而开发...

  • 贪心：jump 游戏（获取最少跳跃的次数以及跳跃路径）

    一个数组存储了非负整型数据，数组中的第i个元素a[i]，代表了可以从数组第i个 位置最多向前跳跃a[i]步;已知数组各元素的情况下，求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置，返回最少跳跃的次数以及跳跃过程的路径（以数组下标标识） 例如: nums = [2, 3, 1, 1, 4] ，可以从nums[0] = 2...

©2024 11GX.COM