P2654 原核生物培养
在洛谷打开一看就一道蓝题——提高+/省选-，看起来有点难度，实际上很简单。
这是一道环形dp+堆排序的题目。
我们把它分为两个部分，一个是排序部分，一个是环形dp部分。
环形dp部分
一看就认为这个是环形dp，还是蓝题，很难。但是我们可以看一下它的前世——NOI1995石子合并。
状态转移方程不用看就知道是求合并石子最小得分。
我们设 \(dp[i][j]\) 是第 \(i\) 个生物至第 \(j\) 个生物互相残杀所消耗酶最小值，\(d(i,j)\) 是 \(i\) 到 \(j\) 生物数量和，设 \(k\) 为生物的分界线，则——
\(dp[i][j]=min(dp[i][j],dp[i][k+dp[k+1][j]+d(i,j)])\)
那么 \(d(i,j)\) 怎么求？前缀和！
但是还有一个坑，那就是这是环形，所以需要复制一个数组
此处代码展示：
int a[31],dp[40][40];
signed main(){
...//前面省略一些代码
for(;p<=k;p=-~p){
...//省略初始化和输入等其它与此无关的东西
for(i=1;i<=m1;i=-~i)a[i]+=a[i-1],dp[i][i]=0;//前缀和操作
/*dp[i][i]=0 是初始化*/
md=0x7f7f7f;
for(len=2;len<=m;len=-~len)
for(i=1,j=i+len-1;i<=m1&&j<=m1;i=-~i,j=i+len-1)
for(t=i;t<j;t=-~t)dp[i][j]=min(dp[i][j],dp[i][t]+dp[t+1][j]+a[j]-a[i-1]);
for(i=1;i<=m;i=-~i)md=min(md,dp[i][i+m-1]);//求最小值
}
...//省略后面的内容
}
维护最小值
堆
可以直接用STL，但我们可以手写堆（考场上应该没人这么干吧）
我们都知道，堆就是一个二叉树。在此题目中，我们需要的是小根堆（最小的永远在堆顶）。
在这道题目中，我们只需要两个操作——插入和删除。
插入
我们将二叉树末尾插入一个数字，然后在逐级比较。一个数的根节点是它自己的二分之一（向下取整）。
struct SD{
inline void push(int x){
tree[++len]=x;
if(len==1)return;
int k=len;
int next;
while(k>1){
next=k>>1;
if(tree[k]>=tree[next])return;
swap(tree[k],tree[next]);
k=next;
}
}
int len,tree[200005];
};
删除
我们直接将堆顶赋值为末尾，再将最后一位设为 \(0\) ，序列减 \(1\) ，最后进行操作。
struct SD{
inline void pop(){
int k(1),next,x;
x=tree[1];
tree[1]=tree[len--];
while((k<<1)<=len){
next=k<<1;
if(next<len&&tree[next+1]<tree[next])next=-~next;
if(tree[k]<=tree[next])return;
swap(tree[k],tree[next]);
k=next;
}
}
int len,tree[200005];
};
冒泡排序
先sort一遍，剩下每一次操作中我们要取最小值，我们可以采用冒泡排序。
每一次合并，只有两个最小的数变成一个较大的数。不妨设这个数为\(a_i\) ，如果 \(a_i<a_{i+1}\) ，我们交换这两个数，如果 \(a_i\ge a{i+1}\) ，说明数组 \(a\) 已经有序，可以直接跳出循环。
详见这道题
队列
这种时间复杂度是 \(O(n)\) 。
我们也是先sort一遍，然后用两个队列。排序的结果放进第一个当中，合并的结果放在第二个当中，每次选取从两个队列队头最小的合并。
详见这道题（不要用桶排序，会MLE的！）
还有很多做法来维护最小值，大家可以自己去看。
代码
我就直接从之前在洛谷写的题解上复制下来。
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<iostream>
using std::swap;
using std::min;
typedef long long LL;
namespace FastIo{
static char buf[100000],*p1=buf,*p2=buf;
#define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
struct QIO{
inline void read(int &x){
x=0,ch=gc;
while(!isdigit(ch))ch=gc;
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
}
inline void write(LL a){
while(a){num[++num[0]]=a%10;a/=10;}
while(num[0])putchar(num[num[0]--]^48);
}
int num[30];
char ch;
}qrw;
}
using namespace FastIo;
struct SD{
SD(){len=0;}
inline bool empty(){return !len;}
inline int top(){return tree[1];}
inline void push(int x){
tree[++len]=x;
if(len==1)return;
int k=len;
int next;
while(k>1){
next=k>>1;
if(tree[k]>=tree[next])return;
swap(tree[k],tree[next]);
k=next;
}
}
inline void pop(){
int k(1),next,x;
x=tree[1];
tree[1]=tree[len--];
while((k<<1)<=len){
next=k<<1;
if(next<len&&tree[next+1]<tree[next])next=-~next;
if(tree[k]<=tree[next])return;
swap(tree[k],tree[next]);
k=next;
}
}
int len,tree[200005];
}st;//详见洛谷题目：堆
int a[31],dp[40][40];
signed main(){
register int i(1),j,p(1),len,t;
int n,m,k,kkk,md,m1;
LL ans(0);
qrw.read(n);
qrw.read(m);
qrw.read(k);
m1=m<<1;//注意本题是环形，此处是把原环复制了一遍,dp也是一样
for(;i<=n;i=-~i){
qrw.read(kkk);
st.push(kkk);
}//此处kkk变量表示物体的重量
for(;p<=k;p=-~p){
memset(dp,0x7f7f,sizeof(dp));
memset(a,0,sizeof(a));
for(j=1;j<=m;j=-~j){
qrw.read(kkk);//此处的kkk表示物体的位置
a[kkk+m]=a[kkk]=st.top();
st.pop();
}
for(i=1;i<=m1;i=-~i)a[i]+=a[i-1],dp[i][i]=0;//忘记初始化了，当时一直卡住了。
/*a[i]+=a[i-1] 此处不想建另一个数组，就简写了，其他作者可能是格外建一个一维数组s，对s进行前缀和操作，这样可以更省时间，但在此题的数据范围就不用了。*/
st.push(a[m]);//无论怎么吃总重量都不变
md=0x7f7f7f;
for(len=2;len<=m;len=-~len){//此处是确定范围
for(i=1,j=i+len-1;i<=m1&&j<=m1;i=-~i,j=i+len-1){
for(t=i;t<j;t=-~t){
dp[i][j]=min(dp[i][j],dp[i][t]+dp[t+1][j]+a[j]-a[i-1]);//详见石子合并
}
}
}
for(i=1;i<=m;i=-~i)md=min(md,dp[i][i+m-1]);//详见石子合并
ans+=md;
}
qrw.write(ans);
exit(0);
return 0;
}