关注
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 评论
相关推荐
05-25 12:52
中国石油大学(华东)青岛校区 Java 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 聊聊这家公司值得去吗 #
228763次浏览 2156人参与
# 职场上哪些事情令人讨厌 #
16431次浏览 80人参与
# 你认为哪个岗位找工作最卷 #
8211次浏览 29人参与
# 职场人,说说你的烦心事 #
8162次浏览 63人参与
# 一人一个landing小技巧 #
77882次浏览 1111人参与
# 秋招最大的收获是什么? #
33748次浏览 296人参与
# kpi面有什么特征 #
29139次浏览 164人参与
# 为了找工作你投递了多少公司? #
7753次浏览 102人参与
# 职场破防瞬间 #
234655次浏览 2124人参与
# 大家每天通勤多久? #
41800次浏览 328人参与
# tplink提前批进度交流 #
162493次浏览 1375人参与
# 许愿池 #
282978次浏览 2868人参与
# 聊聊你的职场新体验 #
157181次浏览 1367人参与
# 找工作前vs找工作后的心路变化 #
9516次浏览 101人参与
# 经纬恒润求职进展汇总 #
118824次浏览 1027人参与
# 入职第一天,你准备什么时候下班 #
55305次浏览 351人参与
# 通信硬件牛牛的实习日记 #
7040次浏览 65人参与
# 硬件人你反向读研了吗 #
41697次浏览 629人参与
# 职场吐槽大会 #
204553次浏览 1627人参与
# 好未来求职进展汇总 #
17988次浏览 153人参与