爱吃葱花饼的刹那 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]来更新答案。 应该就是这样了,一开始想复杂了,结果最后想出来没时间写了):
投递hulu等公司10个岗位 >
0 点赞 评论 收藏
分享
网易笔试 https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/ 基础题是这个,礼物的最大价值,很简单,动规直接搞定 但是这个是拿一次的方案 现在是说有2个人,同时开始拿,问2个人从左上到右下走一次加起来最多能拿多少 我觉得2个人同时拿和每个人依次拿是一样的,就是第一个先走一次,第二个再走一次,然后把两个人的结果加起来即可。 我的思路是: 第一个人先走,记录拿的路径,然后把路径上的礼物价值置为0 第二个人再拿。 ...
牛客403581968号:每次都拿最大的不一定结果最优,因为每个人只能往右或者往下走,并不能回头。 这道题可以两个人一起动态规划,dp(i,j,k,l)表示第一个人在i j 第二个人在k l的最大价值,dp(i j k l)的上一个状态是两个人分别在上面的格子或者左边的格子,总共四种可能取一个最大值然后加上(i j)和(k l)格子里的价值就行。
投递网易等公司10个岗位 >
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客企业服务