因?yàn)閮蓚€(gè)人方案的對(duì)稱(chēng)性，可以將$k$除以$2$，轉(zhuǎn)化為在$n-1$個(gè)間隔中設(shè)置若干斷點(diǎn)，求第$k$小的增量。

對(duì)于選中的相鄰的斷點(diǎn)$(a,a+1)$和$(b,b+1)$，增量為$|x_a-x_{b+1}|$。

將絕對(duì)值拆開(kāi)，用可持久化權(quán)值線段樹(shù)優(yōu)化建圖，然后求$k$短路即可。

時(shí)間復(fù)雜度$O(n\log^2n+k\log k)$。

?

#include<cstdio> #include<algorithm> #include<queue> #include<vector> using namespace std; typedef long long ll; typedef pair<ll,int>P; const int MAXN=10010,N=400000,M=2000000; const ll inf=1LL<<60; int n,K,i,a[MAXN],b[MAXN],T0,T1,l[N],r[N],tot;ll base,ans; namespace G{ int n,m,i,S,T,g[N],v[M],u[M],w[M],nxt[M],f[N],h[N],tot;ll d[N];bool is[M],vis[N]; struct Node{int l,r,d;P v;Node(){}Node(int _l,int _r,int _d,P _v){l=_l,r=_r,d=_d,v=_v;} }pool[M*4]; inline int build(P v){pool[++tot]=Node(0,0,0,v);return tot; } int merge(int a,int b){if(!a||!b)return a+b;if(pool[a].v>pool[b].v)swap(a,b);int x=++tot;pool[x]=pool[a];pool[x].r=merge(pool[a].r,b);if(pool[pool[x].l].d<pool[pool[x].r].d)swap(pool[x].l,pool[x].r);pool[x].d=pool[x].r?pool[pool[x].r].d+1:0;return x; } void cal(int x){if(vis[x])return;vis[x]=1;d[x]=inf,f[x]=0;if(x==T){d[x]=0;return;}for(int i=g[x];i;i=nxt[i]){cal(u[i]);if(d[u[i]]+w[i]<d[x])d[x]=d[u[i]]+w[i],f[x]=i;} } void dfs(int x){if(!f[x]||vis[x])return;vis[x]=1;dfs(u[f[x]]);h[x]=merge(h[x],h[u[f[x]]]); } inline void add(int x,int y,int z){if(!x||!y)return;v[++m]=x;u[m]=y;w[m]=z;nxt[m]=g[x];g[x]=m; } void solve(){for(i=1;i<=n;i++)cal(i);ans=d[S];if(K==1)return;K--;for(i=1;i<=n;i++)vis[i]=0,is[f[i]]=1;for(i=1;i<=m;i++)if(!is[i]&&d[u[i]]<inf)h[v[i]]=merge(h[v[i]],build(P(w[i]-d[v[i]]+d[u[i]],u[i])));for(i=1;i<=n;i++)dfs(i);priority_queue<P,vector<P>,greater<P> >q;ll x,y;y=h[S];if(y)q.push(P(d[S]+pool[y].v.first,y));while(!q.empty()&&K){K--;P t=q.top();q.pop();ans=t.first;x=t.second,y=pool[x].l;if(y)q.push(P(ans-pool[x].v.first+pool[y].v.first,y));y=pool[x].r;if(y)q.push(P(ans-pool[x].v.first+pool[y].v.first,y));y=h[pool[x].v.second];if(y)q.push(P(ans+pool[y].v.first,y));} } } int ins(int x,int a,int b,int c,int X,int W){int y=++tot;if(a==b){G::add(X,y,W);return y;}int mid=(a+b)>>1;if(c<=mid)l[y]=ins(l[x],a,mid,c,X,W),r[y]=r[x];else l[y]=l[x],r[y]=ins(r[x],mid+1,b,c,X,W);G::add(l[y],y,0),G::add(r[y],y,0);return y; } void ask(int x,int a,int b,int c,int d,int X,int W){if(!x)return;if(c<=a&&b<=d){G::add(x,X,W);return;}int mid=(a+b)>>1;if(c<=mid)ask(l[x],a,mid,c,d,X,W);if(d>mid)ask(r[x],mid+1,b,c,d,X,W); } int main(){scanf("%d%d",&n,&K);K=(K+1)/2;for(i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];base+=abs(a[i]-a[i-1]);}sort(b,b+n+1);for(i=0;i<=n;i++)a[i]=lower_bound(b,b+n+1,a[i])-b;G::S=1;G::T=2;tot=2;G::add(1,2,0);for(i=1;i<n;i++){int x=++tot,w=-abs(b[a[i]]-b[a[i+1]]);G::add(1,x,w+abs(b[a[i+1]]));G::add(x,2,0);ask(T0,0,n,0,a[i+1],x,w+b[a[i+1]]);if(a[i+1]<n)ask(T1,0,n,a[i+1]+1,n,x,w-b[a[i+1]]);T0=ins(T0,0,n,a[i],x,-b[a[i]]);T1=ins(T1,0,n,a[i],x,b[a[i]]);}G::n=tot;G::solve();return printf("%lld",ans+base),0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/clrs97/p/7925348.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ3945 : 无聊的邮递员的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。