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;
}

原文地址：http://www.cnblogs.com/SHOJYS/p/Prokaryotic_culture.html