题解 | #codeforces#
小小粉刷匠
https://ac.nowcoder.com/acm/problem/16129
这道题怎么想到是区间dp的。
对于长度为1的区间,很容易想到是1,
对于长度等于2的区间,我们要考虑两个因素,1是刷子的长度,2是两个区间
如果超出了刷子的长度,很明显答案要加1,
如果明显答案可以继承,
再考虑长度为3的刷子的时候,也是一样 不妨假设断点设在2位子如果 这里k从左到右,左开右闭,等于f[i+1][k]+f[k+1][j],即可以从f[k+1][j]上继承过来 这里f[i+1][k]再i=k时为0
如果长度大于k的话,则拆分成两个区间取最小值