自动搬运

查看原文

来自洛谷，原作者为

	kkksc03 洛谷吉祥物 DA✩ZE

搬运于2025-08-24 21:40:04，当前版本为作者最后更新于2015-11-01 22:34:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

合并果子+石子归并。

取出最小的m个有两种办法，一是堆，而是开第二个队列保证有序（参看合并果子题解。）

堆就不用说了。

新开一个队列就是把剩下的那个放入第二个队列，然后再取就去两个队列中最小的m个。第二个队列一定是有序的。

然后dp

假设有菌AiAi+1……Aj需要合并的最小消耗,简记为F[i,j].由于是环形的，j最大可以是2*m-1

当i=j时,表示只有一堆石头,不能合并,因此得分为零,所以F[i,j]=0;

当i<j时,可利用最优子结构性质来计算F[i][j],

F[i,j]=F[i,k]+F[k+1,j]+totalValue(i,j)(i<=k<j)