关注
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 评论
相关推荐
点赞 评论 收藏
分享
03-16 16:31
湖南工商大学 Java 点赞 评论 收藏
分享
03-05 12:23
西安电子科技大学 算法工程师 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 你的实习产出是真实的还是包装的? #
35127次浏览 433人参与
# 牛友的志愿填报指南 #
63004次浏览 484人参与
# 厦门银行科技岗值不值得投 #
15675次浏览 359人参与
# 你的实习什么时候入职 #
366751次浏览 2355人参与
# 学历VS实习,哪个更重要? #
1687次浏览 49人参与
# 工作上你捅过哪些篓子? #
68315次浏览 315人参与
# uu们,春招你还来吗? #
63080次浏览 738人参与
# 面试紧张时你会有什么表现? #
34016次浏览 207人参与
# 面试中,你被问过哪些奇葩问题? #
96195次浏览 1264人参与
# 面试被问到不会的问题,你怎么应对? #
25834次浏览 648人参与
# 你都用vibe coding做过什么? #
21808次浏览 813人参与
# 机械人,签完三方你在忙什么? #
83929次浏览 266人参与
# 你觉得大几开始实习最合适? #
29997次浏览 309人参与
# AI Coding实战技巧 #
15411次浏览 299人参与
# 你见过哪些招聘隐形歧视? #
24810次浏览 214人参与
# 国庆前的秋招小结 #
291243次浏览 1742人参与
# 哔哩哔哩笔试 #
35131次浏览 142人参与
# 如果人生可以debug你会改哪一行? #
12985次浏览 167人参与
# 秋招特别不鸣谢 #
93222次浏览 685人参与
# 应届生被毁约被毁意向了怎么办 #
65362次浏览 313人参与
# 海康威视求职进展 #
132284次浏览 551人参与
查看21道真题和解析