记录编号	96869	评测结果	AAAAAAAAAA
题目名称	山顶问题	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2014-04-15 21:03:37	内存使用	23.21 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
const int SIZEN=100010,SIZEK=26;
const ll INF=1e15;
int N,K;
int H[SIZEN]={0};
vector<int> c[SIZEN];
int SN=0;//片层的数量
class SLICE{
public:
	int head,bot,h,id;//起点,终点,最低点高度,层高,结点编号
};
int base[SIZEN]={0};//压在哪个上
int deg[SIZEN]={0};
ll V[SIZEN]={0};
//算法参见周戈林论文
ll f[SIZEN][SIZEK]={0};
int S;
void DFS(int x){
	for(int i=0;i<=K;i++) f[x][i]=INF;
	if(!c[x].size()){
		f[x][0]=V[x];
		f[x][1]=0;
		return;
	}
	f[x][0]=0;
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i];
		DFS(u);
		for(int j=K;j>=0;j--){
			ll w=INF;
			for(int k=j;k>=0;k--){
				w=min(w,f[x][k]+f[u][j-k]);
			}
			f[x][j]=w;
		}
	}
	if(x!=S){
		f[x][1]=min(f[x][1],f[x][0]);
		f[x][0]+=V[x];
	}
}
void work(void){
	for(int i=1;i<=SN;i++){
		deg[base[i]]++;
		c[base[i]].push_back(i);
		if(!base[i]) S=i;
	}
	int sum=0;
	for(int i=1;i<=SN;i++) if(i!=S&&!deg[i]) sum++;
	if(sum<=K){
		printf("0\n");
		return;
	}
	DFS(S);
	printf("%lld\n",f[S][K]);
}
void makegraph(void){
	vector<SLICE> st;
	st.push_back((SLICE){0,0,1,0});
	for(int i=1;i<=N+1;i++){
		while(st.back().bot>H[i]){//上方的诸片层结束,出栈
			SLICE &T=st.back();
			V[T.id]=(i-T.head)*T.h;
			st.pop_back();
		}
		SLICE &T=st.back();
		if(T.bot<=H[i]&&T.bot+T.h-1>H[i]){
			V[T.id]=(i-T.head)*(T.bot+T.h-1-H[i]);//被分割,新建片层
			SN++;
			base[SN]=base[T.id];
			base[T.id]=SN;
			T.h=H[i]-T.bot+1,T.id=SN;
		}
		else if(T.bot+T.h-1<H[i]){
			SLICE P;
			P.head=i,P.bot=T.bot+T.h,P.h=H[i]-P.bot+1,P.id=++SN;//新建片层
			base[SN]=T.id;
			st.push_back(P);
		}
	}
}
void read(void){
	scanf("%d%d",&N,&K);
	for(int i=1;i<=N;i++) scanf("%d",&H[i]);
}
int main(){
	freopen("peaks.in","r",stdin);
	freopen("peaks.out","w",stdout);
	read();
	makegraph();
	work();
	return 0;
}