爱吃葱花饼的刹那 level
获赞
3
粉丝
2
关注
2
看过 TA
11
暨南大学
2022
自然语言处理
IP属地:北京
暂未填写个人简介
私信
关注
第三题暴力法只A了9%,实在不知道怎么DP      有大佬么,求指教~~~
JianRon:题意转化成:给一个数组然后找满足两个要求的最大的子段和,两个要求分别是: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]来更新答案。 应该就是这样了,一开始想复杂了,结果最后想出来没时间写了):
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客网在线编程
牛客网题解
牛客企业服务