Post Office

Post Office

在x数轴上,给出v个递增的正整数坐标\(\{a_i\}\),请寻找p个点,使坐标到点的最短距离之和最小,\(v\leq 300,p\leq 30\)。

(注意,此题证明过于复杂,不能保证证明完全严谨和正确,如有看不懂,很有可能是打错了,请联系作者)

step1

从答案思考问题,发现必然是连续的几个点,管一段的坐标,这是区间划分模型,设\(f[i][j]\)表示前j个坐标到前i个点的最短距离之和最小值,\(w[i][j]\)为在第i个坐标到第j个坐标中选择一个点让第i个坐标到第j个坐标到这个点距离之和的最小值(\(s_i=\sum_{j=1}^ia_j\),即a的前缀和)。

\[f[i][j]=\min_{0\leq k<j}\{f[i-1][k]+w[k+1][j]\}\]

边界:\(f[i][i]=0,i=0,1,2,..,v\)
答案:\(f[p][v]\)

显然\(w[i][j]=\sum_{k=i}^j|a_k-a_m|(m=\frac{i+j}{2})=[(a_j-a_m)+...+(a_m-a_m)+...\)

\(+(a_m-a_i)]=(a_j+...+a_{m+1})-(a_m+...+a_i)+[m-i+1-(j-m)]\)

\(a_m=(s_j-s_m)-(s_m-s_{i-1})+(2m-i-j+1)a_m=s_j-2s_m+s_{i-1}+(2m-i-j+1)a_m\)

于是我们可以实现维护出w,然后进行转移即可,时间复杂度\(O(pv^2)\)

参考代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
using namespace std;
int a[350],s[350],mid[350][350],
    dp[35][350];
template<class free>
il free Min(free a,free b);
int main(){
    int v,p;
    scanf("%d%d",&v,&p);
    for(int i(1);i<=v;++i)
        scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
    for(int i(1),j,m;i<=v;++i)
        for(j=i+1;j<=v;++j)
            m=(i+j)/2,mid[i][j]=s[j]
                -s[m]-(s[m]-s[i-1])+a[m]*(2*m-i+1-j);
    memset(dp,1,sizeof(dp)),dp[0][0]=0;
    for(int i(1),j,k;i<=p;++i)
        for(dp[i][0]=0,j=1;j<=v;++j)
            for(k=0;k<j;++k)
                dp[i][j]=Min(dp[i][j],dp[i-1][k]+mid[k+1][j]);
    printf("%d",dp[p][v]);
    return 0;
}
template<class free>
il free Min(free a,free b){
    return a<b?a:b;
}

setp2

但是如果你还有梦想,想要优化,二进制(拆分,压缩,倍增)显然不行,我们也没必要维护区间和,而栈与队列不适用,单调性维护平衡树,单调队列,双堆对顶,二分查找,离散化一个也不行,式子对于矩阵快速幂和斜率优化太过于复杂,考虑四边形不等式,关键在证明w满足四边形不等式


求证:w满足四边形不等式

证明:

现在要证明\(i<j,w[i][j+1]+w[i+1][j]\geq w[i][j]+w[i+1][j+1]\)

即证明(设各自中位数\(m_1,m_2,m_3,m_4\))

$s_{j+1}-2s_{m_1}+s_{i-1}+(2m_1-i-j)a_{m_1}+s_j-2s_{m_2}+s_{i}+(2m_2-i-j)a_{m_2}\geq $
\(s_j-2s_{m_3}+s_{i-1}+(2m_3-i-j+1)a_{m_3}+s_{j+1}-2s_{m_4}+s_{i}+(2m_4-i-j-1)a_{m_4}\)

即证明

$-2s_{m_1}+(2m_1-i-j)a_{m_1}-2s_{m_2}+(2m_2-i-j)a_{m_2}\geq $
\(-2s_{m_3}+(2m_3-i-j+1)a_{m_3}-2s_{m_4}+(2m_4-i-j-1)a_{m_4}\)

已知\(m_1=\frac{i+j+1}{2},m_2=\frac{i+j+1}{2},m_3=\frac{i+j}{2},m_4=\frac{i+j+2}{2}\)

I. \(i+j\in\)奇

有\(m_1=m_2=m_4=m_3+1\),即证明

\(-2s_{m_2}+(2m_2-i-j+1)a_{m_2}\geq -2s_{m_3}+(2m_3-i-j+1)a_{m_3}\)

\(-2a_{m_2}+(2m_2-i-j+1)a_{m_2}\geq (2m_3-i-j+1)a_{m_3}\)

\((2m_2-i-j-1)a_{m_2}\geq (2m_3-i-j+1)a_{m_3}\)

\((2(m_3+1)-i-j-1)a_{m_2}\geq (2m_3-i-j+1)a_{m_3}\)

\((2m_3-i-j+1)a_{m_2}\geq (2m_3-i-j+1)a_{m_3}\)

\(a_{m_2}\geq a_{m_3}\)

因为坐标递增,显然\(a_{m_2}\geq a_{m_3}\),于是得证

II. $i+j\in $偶

同理

\(m_1=m_2=m_3=m_4-1\),即证

\(-2s_{m_2}+(2m_2-i-j-1)a_{m_2}\geq-2s_{m_4}+(2m_4-i-j-1)a_{m_4}\)

\((2m_2-i-j-1)a_{m_2}\geq-2a_{m_4}+(2m_4-i-j-1)a_{m_4}\)

\((2m_2-i-j-1)a_{m_2}\geq(2(m_2+1)-i-j-3)a_{m_4}\)

\((2m_2-i-j-1)a_{m_2}\geq(2m_2-i-j-1)a_{m_4}\)

\((i+j-i-j-1)a_{m_2}\geq(i+j-i-j-1)a_{m_4}\)

\(-a_{m_2}\geq -a_{m_4}\)

\(a_{m_2}\leq a_{m_4}\)

显然成立

总上所素,根据四边形不等式判定定理,易知w满足四边形不等式


因此枚举i的话,根据一维线性递推决策递增定理,易知决策点单调递增,我们只要用单调队列维护三元组即可,时间复杂度\(O(pvlog_2^v)\)

参考代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
using namespace std;
struct san{
    int l,r,p;
}T[350];
int a[350],s[350],mid[350][350],
    dp[35][350],L,R;
il int dfs(int,int,int);
template<class free>
il free Min(free a,free b);
int main(){
    int v,p;
    scanf("%d%d",&v,&p);
    for(int i(1);i<=v;++i)
        scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
    for(int i(1),j,m;i<=v;++i)
        for(j=i+1;j<=v;++j)
            m=(i+j)/2,mid[i][j]=s[j]
                -s[m]-(s[m]-s[i-1])+a[m]*(2*m-i+1-j);
    memset(dp,1,sizeof(dp)),dp[0][0]=0;
    for(int i(1),j,k;i<=p;++i){
        L=R=1,T[1].l=1,T[1].r=v,T[1].p=0;
        for(dp[i][0]=0,j=1;j<=v;++j){
            dp[i][j]=dp[i-1][T[L].p]+mid[T[L].p+1][j];if(++T[L].l>T[L].r)++L;
            while(L<=R&&dp[i-1][T[R].p]+mid[T[R].p+1][T[R].l]>=
                  dp[i-1][j]+mid[j+1][T[R].l])--R;T[++R].r=v,T[R].p=j;
            if(L<R){T[R].l=dfs(R-1,j,i-1),T[R-1].r=T[R].l-1;if(T[R].l>T[R].r)--R;}
        }
    }
    printf("%d",dp[p][v]);
    return 0;
}
il int dfs(int t,int p,int i){
    int l(T[t].l),mid,r(T[t].r);
    while(l<=r){
        mid=l+r>>1;
        if(dp[i][T[t].p]+::mid[T[t].p+1][mid]<
           dp[i][p]+::mid[p+1][mid])l=mid+1;
        else r=mid-1;
    }return l;
}
template<class free>
il free Min(free a,free b){
    return a<b?a:b;
}

step3

注意到i,j可以看成一段区间,因为\(i\leq j\),于是由于w满足四边形不等式,边界\(f[i][i]=w[i][i]=0\),而且w满足包含递增


求证:w满足包含递增

证明:

假设增加一个坐标可以让比不增加一个坐标结果优秀,那么直接用增加一个坐标的方案替换不增加一个坐标的方案,会让结果更优秀,矛盾,得证。


于是根据二维递推判定定理,易知f满足四边形不等式,然后又二维递推决策递增定理,容易知道(设\(P[l][r]\)为\(f[l][r]\)的最优决策点),\(P[l][r-1]\leq P[l][r]\leq P[l+1][r]\),于是我们可以优化成\(O(n^2)\)。

参考代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
using namespace std;
int x[550],s[550],mid[550][550],
    dp[550][550],P[550][550];
template<class free>
il free Min(free,free);
int main(){
    int v,p;scanf("%d%d",&v,&p);
    memset(dp,1,sizeof(dp));
    for(int i(1),j,m;i<=v;++i){
        scanf("%d",&x[i]),s[i]=s[i-1]+x[i];
        for(j=i-1;j;--j)
            m=i+j>>1,mid[j][i]=s[i]-
                s[m]*2+s[j-1]+(2*m-j-i+1)*x[m];
        P[i][i]=i-1,dp[i][i]=0;
    }dp[0][0]=0;
    for(int i,j(1),k;j<=v;++j)
        for(i=j-1;i;--i)
            for(k=P[i][j-1];k<=P[i+1][j];++k)
                if(dp[i][j]>dp[i-1][k]+mid[k+1][j])
                    dp[i][j]=dp[i-1][k]+mid[k+1][j],P[i][j]=k;
    printf("%d",dp[p][v]);
    return 0;
}
template<class free>
il free Min(free a,free b){
    return a<b?a:b;
}
上一篇:洛谷$P1864\ [NOI2009]$二叉查找树 区间$dp$


下一篇:UOJ #449. 【集训队作业2018】喂鸽子