pascal 划分型DP

答案:1 悬赏:20 手机版

解决时间 2021-11-25 05:07

提问者网友：niaiwoma
2021-11-24 11:12

pascal 划分型DP

最佳答案

五星知识达人网友：洎扰庸人
2021-11-24 11:59

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

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

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

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息