pascal 划分型DP

pascal 划分型DP

有一个非常显然的结论是，如果将小羊按照高度排序，那么最优方案中的每一组都是连续的一段，如果不是这样就可以通过调整获得更加小的结果。

先将所有的羊按照高度排序，F[i][j]表示决策了前i只羊，已经分了j组的最小不整齐度。根据第i只羊是否被划入当前组进行转移，复杂度 O(n*m)追问能给段核心程序吗？ thanks~~ 好的话加悬赏追答给C++的可以吗...追问可以 thanks~追答不好意思一开始想错了，裸的转移还需要枚举上一组的位置复杂度是 n*n*m 无法通过所有数据。应该使用斜率优化解决 复杂度 n*m


给出的代码已经在小数据范围内和暴力对拍无误，我在代码里加了一些注释帮助理解。