人才池是我家
2023-03-25 22:59 美团_后端开发(准入职员工)
关注
从后往前看，dp[n][0]表示以0结尾且前面都满足条件的最小代价，dp[n]可以由dp[n-ka]转移而来，但是其实dp[n-a]的计算也会包含前面的k，所以只需要dp[n][0]=max(dp[n-a][0]+dp[n-a][1])+diff(n-a,n)，diff表示区间内的非0数量，这个可以用前缀和维护，也就是把这段a长度都变为0,然后就像我上面说的dp[n-a][0]也会继续考虑前面a个0的情况所以这么转移没问题。接着就是dp[n][1]=max(dp[n-b][0],dp[n-b][1])+(b-diff(n-b,n))，不存在的地方存-1
查看原帖
3 3
相关推荐
喜欢吃火锅：真的是万万没想到，还因为能识别不出来被挂掉，救命
点赞 评论 收藏
分享
那就小心你的腰子咯 
Momenta公司福利 468人发布 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 实习进度记录 #
227102次浏览 2819人参与
# 考研可以缓解求职焦虑吗 #
8953次浏览 102人参与
# 平安产险科技中心求职汇总 #
245924次浏览 2619人参与
# 非技术er求职现状 #
53210次浏览 389人参与
# 你喜欢工作还是上学 #
29881次浏览 233人参与
# 大学生该如何认清当下的就业环境？ #
25913次浏览 206人参与
# 考研失败就一定是坏事吗？ #
90018次浏览 741人参与
# 浅聊一下我实习的辛苦费 #
211467次浏览 1600人参与
# 机械只有读研才有出路吗？ #
17526次浏览 207人参与
# 找不到好工作选择GAP真的丢人吗 #
50631次浏览 557人参与
# 毕业论文怎么查AI率 #
15575次浏览 1079人参与
# 考研人，我有话说 #
93513次浏览 844人参与
# 秋招白月光 #
107852次浏览 1246人参与
# 我的求职精神状态 #
22963次浏览 412人参与
# 五一出游找搭子 #
6495次浏览 71人参与
# 产品人求职现状 #
203158次浏览 1867人参与
# 一觉醒来，我成论文导师了… #
9692次浏览 183人参与
# 机械人避雷的岗位/公司 #
11772次浏览 68人参与
# 比特大陆工作体验 #
10989次浏览 79人参与
# 通信硬件公司爆料 #
134858次浏览 513人参与
# 如果能重来，就业or读研你选哪个？ #
126469次浏览 1592人参与