【IOI2000】邮局设置问题

现在连基础DP都要看题解和代码才能写出来了，怎么办嘛QAQ

原题：

一些村庄建在一条笔直的高速公路边上，我们用一条坐标轴来描述这条公路，每个村庄的坐标都是整数，没有两个村庄的坐标相同。两个村庄的距离定义为坐标之差的绝对值。我们需要在某些村庄建立邮局。使每个村庄使用与它距离最近的邮局，建立邮局的原则是：所有村庄到各自使用的邮局的距离总和最小。
数据规模：1<=村庄数<=300,  1<=邮局数<=30,  1<=村庄坐标<=10000

用dis表示若使在i-j中选某点建站，这个点到i-j中每个点距离和的最小值

贪心：选i-j的中点是建站是最优的，可以使用显然法证明（逃

f[i][j]表示一直到第i个点，建了j站的最优质

把j的循坏放外面，也就是先枚举建站的数量，状态转移方程为f[k][j-1]+dis[k+1][i] , j-1<=k<i

意思是枚举把站建在j-1到i的情况

感觉NOIP要挂了，怎么办嘛QAQ

代码：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 int n,m,a[];

 int f[][],dis[][];

 int main(){//freopen("ddd.in","r",stdin);

     memset(f,,sizeof(f));

     cin>>n>>m;

     for(int i=;i<=n;i++)  scanf("%d",&a[i]);

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

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

             dis[i][j]=dis[i][j-]+a[j]-a[(i+j)>>];//贪心，若使一段去间到区间内某点距离和最小，则某点取中点

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

         f[i][i]=;

         f[i][]=dis[][i];

     }

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

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

             for(int k=j-;k<i;k++)

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

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

     return ;

 }