题解：P2654 原核生物培养

对于拿出质量最小的 m 个生物，可以用堆，也可以维护一个有序的数列。这里我们使用更方便一些的堆。

之后 dp 出每次操作的最小值，这个 dp 很板子，具体可以参考石子合并。

状态转移方程如下：

其中 w_i 的求和可以用前缀和优化掉。

最后剩下的生物的质量显然为 m 个生物的质量和。将其加入堆，重复进行 k 次操作即可。

细节处理见代码。

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+100,M=50;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
    char c=getchar();ll x=0,f=1;
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
ll m,n,k,a[N],b[M],dp[M][M],ans=0,sum[M];
priority_queue<int,vector<int>,greater<int> > xiao;//小根堆 
int main()
{
    n=read();
    m=read();
    k=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        xiao.push(a[i]);
    }
    while(k--)
    {
        memset(dp,0x3f,sizeof dp);
        memset(sum,0,sizeof sum);
        memset(b,0,sizeof b);
        for(int i=1;i<=m;i++)
        {
            int x=read();
            b[x]=xiao.top();
            b[x+m]=xiao.top();//将环转化成链 
            xiao.pop();
        }
        for(int i=1;i<=m*2;i++)//注意是从1到2m 
        {
            sum[i]=sum[i-1]+b[i];
            dp[i][i]=0;
        }
        for(int l=2;l<=m;l++)
        {
            for(int i=1;i<=2*m-l+1;i++)
            {
                int j=i+l-1;
                for(int p=i;p<j;p++)
                {
                    dp[i][j]=min(dp[i][j],dp[i][p]+dp[p+1][j]+sum[j]-sum[i-1]);//转移方程 
                }
            }
        }
        ll xyz=1145141919810;
        for(int i=1;i<=m;i++)
        {
            xyz=min(xyz,dp[i][i+m-1]);//因为是转化成链处理，所以还要再找到最优的链 
        }
        ans+=xyz;
        xiao.push(sum[m]);//放回去剩下的那个生物 
    }
    cout<<ans;
    return 0;
}