人才池是我家
2023-03-25 22:58 东南大学 Java
关注
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 评论
相关推荐
01-06 16:09
北京交通大学 Java 笑晕 以前面试前准备：背两天八股 刷一天leetcode现在面试前准备：洗头洗脸 吹个好看的造型 找个角度把自己拍的好看点 对着屏幕欣赏自己哈哈哈哈哈
哞客37422655...：别笑！😂 八股不一定会，但颜值先加分，这叫“形而上学”冲！
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 哪些公司开春招了？ #
6218次浏览 97人参与
# 实习教会我的事 #
50870次浏览 396人参与
# 上班以后，你还有哪些坚持的爱好？ #
5283次浏览 149人参与
# 为了实习逃课值吗？ #
61728次浏览 517人参与
# 你都在哪些场所面过试？ #
14339次浏览 191人参与
# 拼多多工作体验 #
44039次浏览 283人参与
# 工作压力大怎么缓解 #
135581次浏览 1201人参与
# AI coding的好用工具分享 #
12794次浏览 285人参与
# 实习怎么做才有更好的产出 #
8678次浏览 180人参与
# 找工作以来，你最看不惯__ #
8088次浏览 199人参与
# 实习生工资多少才算正常？ #
9545次浏览 176人参与
# 你最近因为什么迷茫？ #
26864次浏览 409人参与
# 实习离职怎么跟领导说 #
75341次浏览 418人参与
# 你给AI提过哪些离谱的需求？ #
4451次浏览 143人参与
# 工作一周年分享 #
49624次浏览 254人参与
# 牛客AI文生图 #
19193次浏览 225人参与
# 领导做过最不靠谱的事 #
8697次浏览 170人参与
# xxx岗位的一天 #
41624次浏览 275人参与
# 实习学不到东西怎么办？ #
270866次浏览 2491人参与
# 机械/制造每日一题 #
84483次浏览 1440人参与