POJ 3017 Cut the Sequence （单调队列优化DP） - 水果君の日常 - 博客频道 - CSDN.NET
将一个由N个数组成的序列划分成若干段，要求每段数字的和不超过M，求【每段的最大值】的和 的最小的划分方法，输出这个最小的和。
分析：
方程是：dp[i] = min(dp[j]+maxsum[j+1][i])
但复杂度n*n太高，需要优化。
可以用单调队列+BST优化，其实只需要维护每一段的最大值。
看了这篇题解的：http://blog.csdn.net/muye67/article/details/5999033。
Read full article from POJ 3017 Cut the Sequence （单调队列优化DP） - 水果君の日常 - 博客频道 - CSDN.NET
No comments:
Post a Comment