区间DP
设 \(F_{i,j,0}\) 为 \([i,j]\) 的牛左端的区间最小花费， \(F_{i,j,1}\) 为 \([i,j]\) 的牛右端的区间最小花费。
接着再找到原点 \(O\) ，设为 \(b\) 点，将 \(F_{b,b,0}\) 和 \(F_{b,b,1}\) 设为 \(0\)，其余为极大值（0x3f）。
接来下是动态转移方程:
\[f_{i,j,0}=\min(f_{i+1,j,0}+(in_{i+1}-in_{i})\times(n+i-j),f_{i+1,j,1}+(in_{j}-in_{i})\times(n+i-j))
\]
\[f_{i,j,1}=\min(f_{i,j-1,1}+(in_j-in_{j-1})\times(n+i-j),f_{i,j-1,0}+(in_j-in_i)\times(n+i-j))
\]
最后取结果要再次求最小值，求左端和右端的最小值即为结果。
详见代码：
#include<bits/stdc++.h>
using namespace std;
int in[2001],b,n;
int f[2001][2001][2];
int main()
{
memset(f,0x3f,sizeof(f));
cin>>n;
for(int i=1;i<=n;++i)
cin>>in[i];
in[++n]=0;//标记原点
sort(in+1,in+n+1);
for(int i=1;i<=n;++i)
if(in[i]==0) b=i;//找原点
f[b][b][0]=f[b][b][1]=0;
for(int j=b;j<=n;j++)
for(int i=j-1;i>=1;i--)
{
f[i][j][0]=min(f[i+1][j][0]+(in[i+1]-in[i])*(n+i-j),f[i+1][j][1]+(in[j]-in[i])*(n+i-j));
f[i][j][1]=min(f[i][j-1][1]+(in[j]-in[j-1])*(n+i-j),f[i][j-1][0]+(in[j]-in[i])*(n+i-j));
}
cout<<min(f[1][n][0],f[1][n][1]);
}