任務
解法
我們考慮将每雙鞋按兩鞋的中點排序，然後把鞋子放的就是一段連續的區間了。
現在我們設 f[i][j] 表示前 i 雙鞋子，用了j個鞋櫃，所需要的最小代價，就有
fi,j=mink<i{fk,j−1+w(k+1,i)}
其中 w(k+1,i) 表示把第 k+1 到 i 雙鞋放在一個鞋櫃中的最小代價。
顯然我們要求w(k+1,i)的話，就要知道第 k+1 到 i 雙鞋的分布情況，這個可以用主席樹來維護。
知道了分布情況之後，我們再主席樹中，找出中位數位置；
知道鞋櫃位置之後，然後我們就再利用主席數，統計每隻鞋子到這個位置的距離和。
這樣的時間複雜度為O(n2k∗log)
如果我們先枚舉 j ，再枚舉i，我們發現 fi,j 的決策點 k 不會小于fi′,j的決策點 k′ ，其中 i′<i 。
那麼我們就可以利用決策單調性來維護。
我這裡采用的是分治法：
先算出 fmid,i 的決策點 kmid ，那麼對于左右區間而言，枚舉的決策點就可以減少了。
總的時間複雜度為 O(nk∗log2)
代碼
#include<iostream>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include<string.h>
#define ll long long
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define f(x,y) f[(x)*(m+1)+(y)]
using namespace std;
const char* fin="shoes.in";
const char* fout="shoes.out";
const ll inf=;
const ll maxn=,maxt=maxn*;
ll n,m,f[maxn],num,last,rt[maxn],ans,lim;
struct shoes{
ll x,y;
}a[maxn];
bool cmp(shoes a,shoes b){return (a.x+a.y)/<(b.x+b.y)/;}
struct node{
ll x,l,r,lson,rson;
}c[maxt];
void modify(ll l,ll r,ll t,ll v,ll _t){
ll mid=(l+r)/;
if (l==r){
c[t].x=c[_t].x+;
return;
}
if (v<=mid){
c[t].rson=c[_t].rson;
modify(l,mid,c[t].lson=++num,v,c[_t].lson);
}else{
c[t].lson=c[_t].lson;
modify(mid+,r,c[t].rson=++num,v,c[_t].rson);
}
c[t].x=c[c[t].lson].x+c[c[t].rson].x;
c[t].l=c[c[t].rson].l+c[c[t].lson].l+c[c[t].rson].x*(mid-l+);
c[t].r=c[c[t].lson].r+c[c[t].rson].r+c[c[t].lson].x*(r-mid);
}
ll query(ll l,ll r,ll t,ll v,ll _t){
ll mid=(l+r)/;
if (r<=v) return c[t].r-c[_t].r+(c[t].x-c[_t].x)*(v-r);
if (l>=v) return c[t].l-c[_t].l+(c[t].x-c[_t].x)*(l-v);
return query(l,mid,c[t].lson,v,c[_t].lson)+query(mid+,r,c[t].rson,v,c[_t].rson);
}
ll getmid(ll l,ll r,ll t,ll _t,ll ls,ll rs){
ll mid=(l+r)/,L=c[c[t].lson].x-c[c[_t].lson].x+ls,R=c[c[t].rson].x-c[c[_t].rson].x+rs;
if (l==r) return l;
if (L<R) return getmid(mid+,r,c[t].rson,c[_t].rson,L,rs);
else if (L>R) return getmid(l,mid,c[t].lson,c[_t].lson,ls,R);
else return mid;
}
ll mincost(ll l,ll r){return query(,+,rt[r],getmid(,+,rt[r],rt[l],,),rt[l]);}
void dfs(ll j,ll l,ll r,ll L,ll R){
ll mid=(l+r)/,tmd=;
if (l>r) return;
fo(k,L,min(mid-,R)){
if (f(k,j-)<lim){
ll tmp=f(k,j-)+mincost(k,mid);
if (tmp<f(mid,j)){
f(mid,j)=tmp;
tmd=k;
}
if (n==mid) ans=min(f(mid,j),ans);
}
}
dfs(j,l,mid-,L,tmd);
dfs(j,mid+,r,tmd,R);
}
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%lld%lld",&n,&m);
fo(i,,n){
scanf("%lld%lld",&a[i].x,&a[i].y);
a[i].x+=+;
a[i].y+=+;
}
sort(a+,a+n+,cmp);
memset(f,,sizeof(f));
lim=f[];
ans=f[];
f(,)=;
rt[]=;
fo(i,,n){
modify(,+,rt[i]=++num,a[i].x,rt[i-]);
modify(,+,rt[i],a[i].y,rt[i]);
}
fo(j,,m)
dfs(j,,n,,n);
printf("%lld",ans);
return ;
}