首页 > 数学考试
头像 精神病科黄主任
发表于 2020-03-26 15:51:52
链接:https://ac.nowcoder.com/acm/problem/15553来源:牛客网 题目描述今天qwb要参加一个数学考试,这套试卷一共有n道题,每道题qwb能获得的分数为ai,qwb并不打算把这些题全做完,他想选总共2k道题来做,并且期望他能获得的分数尽可能的大,他准备选2个不连续 展开全文
头像 Meul
发表于 2020-03-27 01:27:40
NC15553 题意 给你n个数,选2个长度为k的连续区间,求他们加起来的和最大为多少? 思路 前缀和预处理,然后利用前缀和计算k个数的最大数为多少,然后预处理从左边遍历到i为止最大的区间长度为k的和为多少,从右边遍历到i为止最大的区间长度为k的和为多少。扫一遍要选的第一个区间,扫的过程如果左右还有 展开全文
头像 LB_tq
发表于 2020-03-26 12:02:11
Solution 由题意可知需要求两段不连续区间,使和最大。 区间求和问题可以想到一个常用算法:前缀和。区间 的和可以用 方便地求出。 预处理序列的前缀和后,如何得知某个位置之前和之后的和最大的区间呢?我们可以使用线性 求得。设 表示位置 之前的最大区间和, 表示位置 之后的最大区间和。 展开全文
头像 神崎兰子
发表于 2020-03-26 19:02:26
首先声明一下,线段树做法对于本题而言无论是复杂度还是代码长度都劣于前缀和+dp做法。笔者也已经写了前缀和dp的题解:https://blog.nowcoder.net/n/1042c69bd06d40b98f69daf8f708b28b之所以写线段树做法,一是因为自己的数据结构很弱,需要练习(本题的 展开全文
头像 pamhip
发表于 2020-03-26 17:07:33
题意 有 个数选两个长度为 的不相交区间,使得他们的和尽量大,求最大和。 分析 我们可以固定一个区间,然后来找另一个区间。记 为 的前缀和在这道题中,我们枚举 ,然后固定右边的区间 ,右边的贡献为 那么,现在就是在 中找长度为 的连续区间的和的最小值。那么我们设 表示 中长度为 的 展开全文
头像 神崎兰子
发表于 2020-03-26 17:54:21
Update:线段树题解已更新:https://blog.nowcoder.net/n/7c67622afee94322af471bf99ff6ed6b 计 为 区间内,所有的 这样的区间中,数之和的最大值。那么只要遍历一遍,当左区间取 时,右区间的最大值可以 读取,即 。所有以上计算均 展开全文
头像 肖战公关团队
发表于 2020-04-02 14:52:41
Statement 今天qwb要参加一个数学考试,这套试卷一共有道题,每道题qwb能获得的分数为,qwb并不打算把这些题全做完,他想选总共道题来做,并且期望他能获得的分数尽可能的大,他准备选个不连续的长度为的区间,即。其中有。 Solution 把题意简单点说:将一个数组分成两个长度均为且不相交 展开全文
头像 平凡的小白
发表于 2020-05-29 09:14:32
戳我传送 题意: 思路 求两个不连续的区间的最大和,很容易想到前缀和,[l,r]的区间和是sum[r]-sum[l-1]。朴素方法一个指针枚举左区间的起点,另一个指针枚举右区间的起点,两层循环复杂度 (n^2),应该会超时。枚举右区间的起点时,可以发现左区间的起点不需要从1开始找,此时的 展开全文
头像 BE-ABLE-N
发表于 2022-01-11 13:59:08
题意 找到两个不连续且长度为k的序列,使这两个序列和最大。 思路 用前缀和记录下前i个元素的和,然后从前往后遍历,依次记录当前序列和最大的值(ma),以及更新两个序列和的最大值(ans)。 可以很容易想到ma = max(ma, a[i] - a[i - k]), ans = max(ans, 展开全文
头像 与人无语
发表于 2020-05-05 14:46:48
在这题我们要选择两个区间 首先我们知道 右区间一定在左区间右边于是 我们枚举i作为分界线 i左边最大的长度为k的的区间 i右边最大的长度为k的的区间解题的思路出来了 那么该如何用程序表达用cnt数组表示前缀和那么i左边的最大区间和表达为 dp1[i]=max(dp1[i-1],cnt[i]-c 展开全文