救命啊,HULU的第三题怎么写。。。

第三题暴力法只A了9%,实在不知道怎么DP

有大佬么,求指教~~~
#hulu笔试##hulu#
全部评论
题意转化成:给一个数组然后找满足两个要求的最大的子段和,两个要求分别是:1、子段里的负数出现的次数不能超过m个,2、总和不超过K。 做法就是:转为前缀和数组pre_sum,m这个限制可以得到一个滑动窗口。在pre_sum上做这个滑动窗口,然后用一个带排序的可重集(在C++里是multiset)来维护窗口里的值。如果窗口的区间范围是[L,R],那就在multiset里找不大于pre_sum[L-1] + k 的最大的值X,用这个X-pre_sum[L-1]来更新答案。 应该就是这样了,一开始想复杂了,结果最后想出来没时间写了):
3 回复 分享
发布于 2022-03-15 20:51
你这暴力法还不如 print(k) 还可以过 27 哈哈
1 回复 分享
发布于 2022-03-15 20:05
dp只通过17%😅
1 回复 分享
发布于 2022-03-15 20:13
我也是用暴力法,全部条件加完也是9%,把最大收益k的条件去掉就变成64%了,很神奇...
点赞 回复 分享
发布于 2022-03-15 20:11

相关推荐

寿命齿轮:实习就一段还拉了,项目一看就不是手搓,学历也拉了,技术栈看着倒是挺好,就是不知道面试表现能咋样。 不过现在才大三,争取搞两端大厂实习,或者一个纯个人项目+一段大厂,感觉秋招还是未来可期。
投递美团等公司10个岗位
点赞 评论 收藏
分享
我是小红是我:学校换成中南
点赞 评论 收藏
分享
评论
1
2
分享
牛客网
牛客企业服务