现在连基础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 ;
}