CSDN学院讲师招募，诚邀您加入！博客Markdown编辑器上线啦那些年我们追过的Wrox精品红皮计算机图书PMBOK第五版精讲视频教程火星人敏捷开发1001问
Broken Necklace(USACO官方)
分类：算法练习
复杂度为O(n2):
官方答案2:复杂度O(n)
Dynamic Programming is good method for solving this problem in O(N). If we consider two copies of the string we easy transform cyclic configuration of the necklace to linear. Now we can compute for each breaking point how many beads of the same color can be collected on the left and on the right from the breaking point. I show how we can compute it only for the left side. For right side it is analogical. Let r[p] and b[p] be the number of red / blue beads that can be collected, when necklace is broken in point p. If we know this and color of next bead (c) we can compute r[p+1] and b[p+1].
r[0] = p[0] = 0 If c = ‘r’ then r[p+1] = r[p] + 1 and b[p+1] = 0because the length of the blue beads is 0. if c = ‘b’ then b[p+1] = b[p] + 1 and r[p+1] = 0 if c = ‘w’ then both length of the red and length of blue beadscan be longer.so r[p+1] = r[p]+1 and b[p+1] = b[p] + 1.
The number of beads that can be collected in breaking point p is then max(left[r[p]], left[b[p]]) + max(right[r[p]], right[b[p]]). And the maximum from this value is answer for the problem.
上一篇Broken Necklace(USACO)下一篇Milking Cows(USACO)
主题推荐猜你在找
查看评论
* 以上用户言论只代表其个人观点，，不代表CSDN网站的观点或立场
核心技术类目
学习会使你永远立于不败之地。
