JZYZOJ1311 邮局设置问题 dp

易得每两个点之间建立邮局的最好位置为两点最中间的点,两点之间如果没有奇数个数的点则中间两个点都可以...(自己画一下图可以看出随着右边点的增大最佳点的增大非常平滑...强迫症一本满足)

 

w[i][j]为i,j两个点之间建立邮局的最小的距离累加和

则w[i][j]=w[i][j-1]+a[j]-a[(i+j)/2]; 

相对于前一个的总距离只需要加上新加入的点到最佳点的距离

(因为最佳点移动的非常平滑啊,要么是不动要么是动了之后相对于前一个邮局位置没什么意义(因为两点之间点数为偶数时中间两个点都可以看做最佳点,所以所有点分别到这两个点的距离和是一样的))

自己画图分析吧我画不出来图几何绘图太难用了席八.....

 

f[j][i]为在前i个点里建立j个邮局的距离累加和

f[j][i]=min(f[j][i],f[j-1][k]+w[k+1][i]);

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 int n,m;

 int a[]={};

 int f[][]={};

 int w[][]={};

 int main(){

     cin>>n>>m;

     for(int i=;i<=n;i++){

         cin>>a[i];

     }

     sort(a+,a++n);

     for(int i=;i<=n;i++){

         for(int j=i+;j<=n;j++){

             w[i][j]=w[i][j-]+a[j]-a[(i+j)/];

         }

     }

     for(int i=;i<=n;i++){

         f[i][i]=;

         f[][i]=w[][i];

     }

     for(int j=;j<=m;j++){

         for(int i=j+;i<=n;i++){

             f[j][i]=;

             for(int k=;k<i;k++){

                 f[j][i]=min(f[j][i],f[j-][k]+w[k+][i]);

             }

         }

     }

     cout<<f[m][n]<<endl;

     return ;

 }