Description
Data Constraint
Solution
這道題我們設出f[j][i]表示目前放了j個鞋櫃，對于前i雙鞋子的最小代價。設g(x,y)表示目前第x雙鞋子到第y雙鞋子放于同一鞋櫃中的最小代價。我們把鞋子按平均值排序，那麼轉移顯然有 f[j][i]=mini−1k=1f[j−1][k]+g(k+1,i) 容易發現g(x,y)其實就是這x到y雙鞋同時放于數軸上，找到這些數的中位數，中位數右邊的數的和減去中位數左邊的數的和即最小代價，這個可以用主席樹來維護，詢問時O( logN )算出。那麼這個算法的複雜度就是O( N2KlogN )。這顯然逾時。
我們考慮優化。我們發現f[j][i]滿足決策單調性，于是我們考慮用分治來完成f[j][i]，即我們每次先枚舉鞋櫃數，然後對鞋子雙數進行分治，每次我們先算出f[j][mid]以及它的決策點x，然後我們在[mid+1,r]的決策顯然不小于x,[l,mid-1]的決策顯然不大于x，按這個思路往下做，時間複雜度O( NKlogN2 )。
證明一下決策單調性
假設f[j][i]的最優決策在f[j-1][k],存在(i’< i)f[j][i’]的最優決策在f[j-1][k’]且i’>k’>k，我們知道在做f[j][i’]時是已經考慮過k，f[j-1][k]+g(k,i’)>f[j-1][k’]+g(k’,i’),做f[j][i]時是已經考慮過k’，f[j-1][k’]+g(k’,i)>f[j-1][k]+g(k,i)。
f[j−1][k]+g(k,i′)>f[j−1][k′]+g(k′,i′),g(k,i′)−g(k′,i′)>f[j−1][k′]−f[j−1][k]……1
f[j−1][k′]+g(k′,i)>f[j−1][k]+g(k,i),g(k,i)−g(k′,i)<f[j−1][k′]−f[j−1][k]……2
由于i’到i的一段鞋子是固定的，是以1,2沖突，說以k’< k。f[j][i]滿足決策單調性。
Code
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=+,mo=+;
struct code{
ll a,b;
}a[maxn];
struct code1{
ll l,r,sum,num;
}f1[maxn*];
ll f[][maxn],g[maxn],d[maxn];
ll n,m,i,t,j,k,l,x,y,z,p,num;
bool cmp(code x,code y){
return x.a+x.b<y.a+y.b;
}
void insert(ll &v,ll v1,ll l,ll r,ll x){
ll mid=(l+r)/;
v=++num;f1[v]=f1[v1];
if (l==r){
f1[v].sum+=l;f1[v].num++;return;
}
if (mid>=x) insert(f1[v].l,f1[v1].l,l,mid,x);
else insert(f1[v].r,f1[v1].r,mid+,r,x);
f1[v].sum=f1[f1[v].l].sum+f1[f1[v].r].sum;f1[v].num=f1[f1[v].l].num+f1[f1[v].r].num;
}
void find(ll l,ll r,ll v,ll v1,ll x){
ll mid=(l+r)/;
if (l==r){
k-=x*l;
return;
}
if (f1[f1[v].l].num-f1[f1[v1].l].num>f1[f1[v].r].num+x-f1[f1[v1].r].num){
k+=f1[f1[v].r].sum-f1[f1[v1].r].sum;
find(l,mid,f1[v].l,f1[v1].l,x+f1[f1[v].r].num-f1[f1[v1].r].num);
}else if (f1[f1[v].l].num-f1[f1[v1].l].num<f1[f1[v].r].num+x-f1[f1[v1].r].num){
k-=f1[f1[v].l].sum-f1[f1[v1].l].sum;
find(mid+,r,f1[v].r,f1[v1].r,x-f1[f1[v].l].num+f1[f1[v1].l].num);
}else{
k+=f1[f1[v].r].sum-f1[f1[v1].r].sum-f1[f1[v].l].sum+f1[f1[v1].l].sum;return;
}
}
void dg(int l,int r,int x,int y){
int mid=(l+r)/,i,j,t;
if (l>r) return;
for (j=x;j<=min(mid-1,y);j++){
k=;
find(,mo*,d[mid],d[j],);
if (f[-p][j]+k<f[p][mid])f[p][mid]=f[-p][j]+k,t=j;
}
dg(l,mid-,x,t);dg(mid+1,r,t,y);
}
int main(){
freopen("shoes.in","r",stdin);freopen("shoes.out","w",stdout);
scanf("%lld%lld",&n,&m);
for (i=;i<=n;i++){
scanf("%lld%lld",&a[i].a,&a[i].b);a[i].a+=mo;a[i].b+=mo;
if (a[i].a>a[i].b) swap(a[i].a,a[i].b);
}
sort(a+,a+n+,cmp);
for (i=;i<=n;i++)
insert(d[i],d[i-],,mo*,a[i].a),insert(d[i],d[i],,mo*,a[i].b);
memset(f,,sizeof(f));f[0][0]=0;
for (i=;i<=m;i++){p=1-p;
for (j=;j<=n;j++)
f[p][j]=;
dg(i,n,i-,n);
}
printf("%lld\n",f[p][n]);
}