首先求出在第i个到第j个村庄中只建立一个邮局的最优距离，用数组dis[i][j]表示。dis[i][j]=dis[i][j-1]+a[j]-a[(i+j)/2]; （村庄位置为a[i]）显然邮局建在中心a[(i+j)/2]最优，如果有两个，建在哪个中心都可以。画画图就可以理解了。然后用数组dp[i][k]表示在前i个村庄中建立k个邮局的最小距离。则
dp[i][k]=min{dp[j][k−1]+dis[j+1][i]|k−1≤j<i}
d
p
[
i
]
[
k
]
=
m
i
n
{
d
p
[
j
]
[
k
−
1
]
+
d
i
s
[
j
+
1
]
[
i
]
|
k
−
1
≤
j
<
i
}
复杂度
O(n2m)
O
(
n
2
m
)
因为dis数组显然符合四边形不等式以及区间包含关系单调，所以我们可以进行四边形不等式优化。时间复杂度肯定是更优了，但具体是多少我并没有分析清楚-,- 可以去看下这个人的分析。
朴素版
int a[N],n,
m,dis[N][N],dp[N][
31];
inline
int read(){
int x=
0,f=
1;char ch=getchar();
while(ch<
'0'||ch>
'9'){
if(ch==
'-')f=-
1;ch=getchar();}
while(ch>=
'0'&&ch<=
'9')
x=
x*10+ch-
'0',ch=getchar();
return x*f;
}
inline
int min(
int x,
int y){
return x<
y?
x:
y;}
int main(){
// freopen(
"a.in",
"r",stdin);
n=
read();
m=
read();memset(dp,
0x3f,sizeof(dp));
for(
int i=
1;i<=n;++i) a[i]=
read();
for(
int i=
1;i<=n;++i)
for(
int j=i+
1;j<=n;++j)
dis[i][j]=dis[i][j-
1]+a[j]-a[i+j>>
1];
for(
int i=
1;i<=n;++i) dp[i][
1]=dis[
1][i];
for(
int k=
2;k<=
m;++k)
for(
int i=k;i<=n;++i)
for(
int j=k-
1;j<i;++j)
dp[i][k]=min(dp[i][k],dp[j][k-
1]+dis[j+
1][i]);
printf(
"%d\n",dp[n][
m]);
return 0;
}
优化版
int a[N],n,
m,dis[N][N],dp[N][
31],K[N][N];
inline
int read(){
int x=
0,f=
1;char ch=getchar();
while(ch<
'0'||ch>
'9'){
if(ch==
'-')f=-
1;ch=getchar();}
while(ch>=
'0'&&ch<=
'9')
x=
x*10+ch-
'0',ch=getchar();
return x*f;
}
inline
int min(
int x,
int y){
return x<
y?
x:
y;}
int main(){
// freopen(
"a.in",
"r",stdin);
n=
read();
m=
read();memset(dp,
0x3f,sizeof(dp));
for(
int i=
1;i<=n;++i) a[i]=
read();
for(
int i=
1;i<=n;++i)
for(
int j=i+
1;j<=n;++j)
dis[i][j]=dis[i][j-
1]+a[j]-a[i+j>>
1];
for(
int i=
1;i<=n;++i) dp[i][
1]=dis[
1][i];
for(
int i=
1;i<=
m;++i) K[n+
1][i]=n-
1;
for(
int j=
2;j<=
m;++j)
for(
int i=n;i>=
1;--i)
for(
int k=K[i][j-
1];k<=K[i+
1][j];++k)
if(dp[k][j-
1]+dis[k+
1][i]<dp[i][j])
dp[i][j]=dp[k][j-
1]+dis[k+
1][i],K[i][j]=k;
printf(
"%d\n",dp[n][
m]);
return 0;
}
