题解 | #codeforces#

小小粉刷匠

https://ac.nowcoder.com/acm/problem/16129

这道题怎么想到是区间dp的。

对于长度为1的区间,很容易想到是1,

对于长度等于2的区间,我们要考虑两个因素,1是刷子的长度,2是两个区间

如果超出了刷子的长度,很明显答案要加1,

如果a[i]==a[i+1]a[i]==a[i+1]明显答案可以继承,

再考虑长度为3的刷子的时候,也是一样 不妨假设断点设在2位子f[i][k],f[k+1][j]f[i][k],f[k+1][j]如果a[i]==a[k+1]a[i]==a[k+1] 这里k从左到右,左开右闭,等于f[i+1][k]+f[k+1][j],即可以从f[k+1][j]上继承过来 这里f[i+1][k]再i=k时为0

如果长度大于k的话,则拆分成两个区间取最小值

全部评论

相关推荐

嵌入式求职之路:可以看我经验😂,https://www.nowcoder.com/share/jump/73221730841876945
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务