当前位置：首页 > 编程日记 > 正文

每日一题 -- 11-1

编程日记 2024-05-10 04:30:00

一天十题选择，一天一道编程，一天一个面试题，一个一个剑指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

输出

题目分析

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

代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int main()
{int n;while (cin >> n){vector<long long> arr(n);for (int i = 0; i<n; i++){cin >> 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; i<n; i++){dp_max[i][1] = arr[i];dp_min[i][1] = arr[i];}for (int i = 0; i<n; i++){for (int j = 2; j<k + 1; 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; i<n; i++){maxnum = max(maxnum, dp_max[i][k]);}cout << maxnum << endl;}return 0;
}

https://www.dkcj.cn/info/5914.html

每日一题 -- 11-1

题目描述

输入描述:

输出描述:

示例1

题目分析

代码

相关文章：

Java中? extends T和? super T的理解

学习Modern UI for WPF

idea的tomcat配置文件在哪里修改_MyBatis配置文件详解

《几何与代数导引》例1.4——定比分点

C#第一个程序Helloworld

Leanote

微软安全新闻聚焦-双周刊第三十四期

mysql如何实现实时存储_OpenResty + Mysql 实现日志实时存储

简易RS232 建模二（接收）

《UNIX高级环境编程》 -- apue.h

mysql 多少个数据库_mysql数据库的几个基本概念

教孩子正确对待分数

canvas初尝试

模板1.0 -- 模板基本原理

[置顶] 我的GB28181标准开发里程碑——基于eXosip的IPC端与SPVMN注册成功

mysql如何避免特殊字符查询_如何避免MySQL中的特殊字符？

visio 2010 修改默认字体字号大小方法

[BZOJ3329] Xorequ

Asp.net中时间格式化的几种方法

centos设置网络自动启动

mysql删除原则_MySQL数据库的增删选查

ubuntu网卡配置

自动化运维工具----ansible

【内核】嵌入式linux内核的五个子系统

git用户文档1 — git基础

MySQL5.7的date类型_Mysql5.7 虚拟列数据类型为DATE时，如何存入数据？

找出字符串中所有数字

Safair 浏览器cllick事件不生效或者需要双击才生效

springboot mysql行锁_SpringBoot基于数据库实现简单的分布式锁

简单shell