有匹配次数限制,求最小代价,这显然是个费用流的模型.每个点暴力和前面的点连匹配边,边数是(n^2)的.
然后发现可以转化成一个set,每次加入一个点,然后入点对set里面的出点连边.这个set可以用主席树实现,然后就主席树优化连边,点数边数都是(nlogn)的,然后就能过了
注意这里连边要把一个点入点拆成两个(a_i,-a_i),出点同理,然后假设(a_i)在set的第(p)位,(a_i)在负权值主席树上连区间([1,p-1]),(-a_i)在正权值主席树上连区间([p+1,n])
然后主席树被分治连边吊打
// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define LL long long
#define db double
using namespace std;
const int N=1e3+10,M=3e4+10,inf=1<<29;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[M<<2],nt[M<<2],c[M<<2],hd[M],tot=1;
LL w[M<<2];
void add(int x,int y,int z,LL zz)
{
if(!y) return;
++tot,to[tot]=y,nt[tot]=hd[x],c[tot]=z,w[tot]= zz,hd[x]=tot;
++tot,to[tot]=x,nt[tot]=hd[y],c[tot]=0,w[tot]=-zz,hd[y]=tot;
}
LL ans,di[M];
int n,W,a[N],b[N],p[N];
bool cmp(int aa,int bb){return a[aa]<a[bb];}
int ps,pt,fw[M],pr[M];
bool v[M];
queue<int> q;
bool csfl()
{
memset(di,0x3f,sizeof(LL)*(pt+3));
di[ps]=0,v[ps]=1,q.push(ps);
fw[pt]=0;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(c[i]>0&&di[y]>di[x]+w[i])
{
di[y]=di[x]+w[i],fw[y]=1,pr[y]=i;
if(!v[y]) v[y]=1,q.push(y);
}
}
v[x]=0;
}
if(!fw[pt]) return 0;
ans+=di[pt];
int x=pt;
while(x!=ps)
{
int i=pr[x];
c[i]-=fw[pt],c[i^1]+=fw[pt];
x=to[i^1];
}
return 1;
}
int rt1,rt2,ch[M][2],t1,t2;
void inst(int o1,int o2,int x,int &tt)
{
int l=1,r=n;
while(l<r)
{
int mid=(l+r)>>1;
if(x<=mid)
{
ch[o1][0]=++tt,ch[o1][1]=ch[o2][1];
add(o1,ch[o1][0],inf,0),add(o1,ch[o1][1],inf,0);
o1=ch[o1][0],o2=ch[o2][0];
r=mid;
}
else
{
ch[o1][0]=ch[o2][0],ch[o1][1]=++tt;
add(o1,ch[o1][0],inf,0),add(o1,ch[o1][1],inf,0);
o1=ch[o1][1],o2=ch[o2][1];
l=mid+1;
}
}
}
void link(int o,int l,int r,int ll,int rr,int x,int y)
{
if(!o) return;
if(ll<=l&&r<=rr){add(x,o,1,y);return;}
int mid=(l+r)>>1;
if(ll<=mid) link(ch[o][0],l,mid,ll,rr,x,y);
if(rr>mid) link(ch[o][1],mid+1,r,ll,rr,x,y);
}
int main()
{
n=rd(),W=rd();
ps=0,pt=n*24+2;
t1=n*2,t2=n*13;
for(int i=1;i<=n;++i) a[i]=rd(),b[i]=i;
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;++i) p[b[i]]=i;
for(int i=1;i<=n;++i)
{
add(ps,i,1,0),add(i,pt,1,W);
int las;
las=rt1,rt1=++t1,inst(rt1,las,p[i],t1);
las=rt2,rt2=++t2,inst(rt2,las,p[i],t2);
if(p[i]>1) link(rt1,1,n,1,p[i]-1,i,a[i]);
if(p[i]<n) link(rt2,1,n,p[i]+1,n,i,-a[i]);
add(t1,i+n,1,-a[i]),add(t2,i+n,1,a[i]);
add(i+n,pt,1,0);
}
while(csfl());
printf("%lld
",ans);
return 0;
}