C++11(clang++ 3.9) 解法, 执行用时: 1594ms, 内存消耗: 2872K, 提交时间: 2020-10-08 22:06:42

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5e4+5,M=8e6+5;
const LL Inf=1e18;
struct mincostmaxflow{
	struct Edge{int to,f,w,nxt;}e[M];
	int s,t,fst[N],tote,pre[N],from[N],q[N<<10],hd,tl;
	LL dis[N],mi[N];bool inq[N];
	void adde(int u,int v,int f,int w){
		e[++tote]=(Edge){v,f,w,fst[u]};fst[u]=tote;
		e[++tote]=(Edge){u,0,-w,fst[v]};fst[v]=tote;
	}
	void init(int ns,int nt){
		s=ns;t=nt;
		memset(fst,-1,sizeof(fst));tote=1;
	}
	bool spfa(){
	    for(int i=1;i<N;i++)dis[i]=Inf,inq[i]=false;
	    dis[s]=0;q[hd=tl=1]=s;inq[s]=true;mi[s]=Inf;
	    while(hd<=tl){
	    	if(hd<tl&&dis[q[hd]]>dis[q[tl]])swap(q[hd],q[tl]);
	        int u=q[hd++];inq[u]=false;
	        for(int i=fst[u],v,w;~i;i=e[i].nxt)if(e[i].f){
	            v=e[i].to;w=e[i].w;
	            if(dis[v]>dis[u]+w){
	                dis[v]=dis[u]+w;mi[v]=min(mi[u],(LL)e[i].f);pre[v]=i;from[v]=u;
	                if(!inq[v])inq[v]=true,q[++tl]=v; 
	            }
	        }
	    }
	    return dis[t]<Inf;
	}
	LL EK(){
		LL res=0;
		while(spfa()){
			for(int i=t;i!=s;i=from[i])e[pre[i]].f-=mi[t],e[pre[i]^1].f+=mi[t];
			res+=(LL)mi[t]*dis[t];
		}
		return res;
	}
}F;
int n,w,s,t,a[N],in[N],out[N],b[N],tot;
void cdq(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1,len=0;
	cdq(l,mid);cdq(mid+1,r);
	for(int i=l;i<=r;i++)b[++len]=a[i];
	sort(b+1,b+len+1);len=unique(b+1,b+len+1)-b-1;
	for(int i=1;i<len;i++)F.adde(tot+i,tot+i+1,1e9,b[i+1]-b[i]),F.adde(tot+i+1,tot+i,1e9,b[i+1]-b[i]);
	for(int i=l,x;i<=r;i++){
		x=lower_bound(b+1,b+len+1,a[i])-b;
		if(i<=mid)F.adde(tot+x,out[i],1,0);else F.adde(in[i],tot+x,1,0);
	}
	tot+=len;
}
int main(){
	scanf("%d%d",&n,&w);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),in[i]=i,out[i]=i+n;
	F.init(s=out[n]+1,t=out[n]+2);tot=t;
	for(int i=1;i<=n;i++)F.adde(s,in[i],1,0),F.adde(out[i],t,1,0),F.adde(in[i],t,1,w);
	cdq(1,n);
	printf("%lld\n",F.EK());
	return 0;
}