人才池是我家
2023-03-25 22:58 美团_后端开发(准入职员工)
关注
T2确实难想，从后往前看，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 评论
相关推荐
投递广联达等公司6个岗位 > 点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 写给毕业5年后的自己 #
10778次浏览 205人参与
# 产品实习，你更倾向大公司or小公司 #
150531次浏览 1931人参与
# 一人一个landing小技巧 #
74458次浏览 1077人参与
# 得物求职进展汇总 #
96361次浏览 805人参与
# 职场捅娄子大赛 #
352831次浏览 3581人参与
# 硬件兄弟们 甩出你的华为奖状 #
103828次浏览 689人参与
# 现在还是0offer，延毕还是备考 #
1030707次浏览 7549人参与
# 产品每日一题 #
43316次浏览 561人参与
# 如何看待offer收割机的行为 #
777417次浏览 6020人参与
# 大城市找工作会更容易吗 #
38093次浏览 333人参与
# 工作中，努力重要还是选择重要？ #
122958次浏览 1537人参与
# 来聊聊你目前的求职进展 #
627283次浏览 6725人参与
# 投格力的你，拿到offer了吗？ #
82188次浏览 571人参与
# 实习吐槽大会 #
48014次浏览 220人参与
# 互联网回暖，腾讯要招5000人！ #
17102次浏览 557人参与
# 我的租房踩坑经历 #
41101次浏览 387人参与
# 26届秋招投递记录 #
6113次浏览 157人参与
# 提前批过来人的忠告 #
103314次浏览 1126人参与
# 为什么国企只招应届生 #
172699次浏览 1140人参与
# 硬件人秋招的第一个offer #
72215次浏览 1110人参与