2022-03-15 20:03
暨南大学 自然语言处理 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 点赞 评论 收藏
分享
2022-03-13 14:17
暨南大学 自然语言处理 0 点赞 评论 收藏
分享
2022-03-05 17:39
暨南大学 自然语言处理 牛客40358196...:每次都拿最大的不一定结果最优,因为每个人只能往右或者往下走,并不能回头。 这道题可以两个人一起动态规划,dp(i,j,k,l)表示第一个人在i j 第二个人在k l的最大价值,dp(i j k l)的上一个状态是两个人分别在上面的格子或者左边的格子,总共四种可能取一个最大值然后加上(i j)和(k l)格子里的价值就行。

0 点赞 评论 收藏
分享
2022-03-05 12:10
暨南大学 自然语言处理 mangoicel:利用前缀后缀记录到0-i和i+1到n的内部子数组最大值,然后枚举分割点

0 点赞 评论 收藏
分享
创作者周榜
更多
关注他的用户也关注了: