题解 P2654 【原核生物培养】

kkksc03 · 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)