这题是一道区间DP
思维难度主要集中在如何预处理距离上
由生活经验得，邮局放在中间显然最优
所以我们可以递推求出\( w[i][j] \)表示i,j之间放一个邮局得距离
然后设出状态转移方程
设\( dp[i][j] \)表示从1开始到i放j个邮局的最短距离
然后转移为：\( dp[i][j]=min(dp[k][j-1]+w[k+1][j],dp[i][j]),i \le k \le j \)
显然是个\( O(n^{3}) \)的DP
能够得40分
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int w[][],dp[][],n,p,x[];
signed main(){
scanf("%lld %lld",&n,&p);
for(int i=;i<=n;i++)
scanf("%lld",&x[i]);
sort(x+,x+n+);
memset(w,0x3f,sizeof(w));
for(int i=;i<=n;i++)
w[i][i]=;
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
w[i][j]=w[i][j-]+x[j]-x[(i+j)/];
memset(dp,0x3f,sizeof(dp));
for(int i=;i<=n;i++)
dp[i][]=w[][i];
for(int i=;i<=p;i++)
dp[i][i]=;
for(int i=;i<=p;i++)
for(int j=i+;j<=n;j++)
for(int k=i-;k<=j;k++){
dp[j][i]=min(dp[j][i],dp[k][i-]+w[k+][j]);
//5 printf("%d %d %d %d\n",i,j,k,dp[j][i]);
}
/*for(int l=1;l<=n;l++)
for(int i=1;i+l<=n;++)
printf("w[%d][%d]=%d\n",i,i+l,w[i][i+l]);*/
printf("%lld\n",dp[n][p]);
return ;
}
然后就是优化
我们可以发现一些显然的性质
\( w[i^{'}][j] \le w[i][j^{'}] , i \le i^{'} \le j \le j^{'} \)
\( w[i][j]+w[i^{'}][j^{'}] \le w[i^{'}][j]+w[i][j^{'}] \)
然后就可以用四边形不等式优化DP了！
然后QwQ
复杂度\( O(n^{2}) \)
没了
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int w[][],dp[][],n,p,x[],s[][];
signed main(){
scanf("%lld %lld",&n,&p);
for(int i=;i<=n;i++)
scanf("%lld",&x[i]);
sort(x+,x+n+);
memset(w,0x3f,sizeof(w));
for(int i=;i<=n;i++)
w[i][i]=;
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
w[i][j]=w[i][j-]+x[j]-x[(i+j)/];
memset(dp,0x3f,sizeof(dp));
for(int i=;i<=n;i++)
dp[i][]=w[][i],s[i][]=;;
for(int i=;i<=p;i++)
dp[i][i]=;
for(int i=;i<=p;i++){
s[n+][i]=n;
for(int j=n;j>=i+;j--)
for(int k=s[j][i-];k<=s[j+][i];k++)
if(dp[j][i]>dp[k][i-]+w[k+][j]){
dp[j][i]=dp[k][i-]+w[k+][j];
s[j][i]=k;
//5 printf("%d %d %d %d\n",i,j,k,dp[j][i]);
}
}
/*for(int l=1;l<=n;l++)
for(int i=1;i+l<=n;++)
printf("w[%d][%d]=%d\n",i,i+l,w[i][i+l]);*/
printf("%lld\n",dp[n][p]);
return ;
}