分析：
对于输出答案真的很好做，然后被输出路径恶心到了。。。
上来先离散化 + 去重简化题目，用 \(v[i]\) 记录权值为 \(i\) 的点，\(a[i]\) 为点 \(i\) 的权值。
那么行径的每一步可以分为两类：
-
从 \(v[i]\) 内的点到 \(v[i+1]\) 的点。
-
从 \(v[i]\) 内的点到 \(v[i]\) 内的点。
设 \(dp[i]\) 为走完了所有权值小于等于 \(a[i]\) 的点后留在了 \(i\) 的最小花费。
设 \(f[i]\) 为走完了所有权值小于 \(a[i]\) 的点(以及 \(i\) 本身)后留在了 \(i\) 的最小花费。
我们发现由 \(dp[x]\) 推出 \(f[y]\) \((a[y]=a[x]+1)\) 便是第一类步，由 \(f[x]\) 推出 \(dp[y]\) \((a[x]=a[y])\)为第二类步。
第一类很好处理：
\[f[y]=\min(dp[x]+\min(abs(x-y),n-abs(x-y)))(y\in v[a[y]-1]) \]\(\min(abs(x-y),n-abs(x-y))\) 即是考虑图是环形，\(f[y]\) 为走完了所有权值小于 \(a[y]\) 的点后留在 \(y\) 的花费，应该由一个已经处理了所有权值小于等于 \(a[y]-1\) 的地方推来的，即是属于 \(v[a[y]-1]\) 的 \(x\) 的 \(dp[x]\)。
第二类：
请不要在意中间的三座火山，两座活火山，一座死火山...那只是心血来潮的产物，大人总是需要我来解释，这让我很心累（。
显然要求从一个点出发然后遍历完所有的点，最后停留在一个点便是从 \(f\) 的状态变为了 \(dp\) 的状态了。
从 \(x\) 出发到 \(y\)。
如果 \(y\) 与 \(x\) 不相邻，显然要求从 \(x\) 出发转一圈后停在与 \(x\) 相邻的一个点后再返回 \(y\)，这必然不会优于直接停留在那个与 \(x\) 相邻的点，因此只用考虑 \(x\) 与 \(y\) 相邻两种情况（左右）了。
code：
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int a[N],b[N],dp[N],f[N];
vector<int>v[N];
int main()
{
int n,cnt=0,m=0,s;
cin>>n>>s;
for(int i=1;i<=n;++i) cin>>a[i],b[++m]=a[i];
sort(b+1,b+n+1);m-=b+m+1-unique(b+1,b+n+1);
for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+m+1,a[i])-b,v[a[i]].push_back(i);
memset(dp,63,sizeof(dp));memset(f,63,sizeof(f));
for(int i=1;i<=m;++i)
{
for(auto x:v[i])
{
if(i==1) {int y=s;dp[x]=min(dp[x],min(abs(x-y),n-abs(x-y)));}
else {for(auto y:v[i-1]) dp[x]=min(dp[x],dp[y]+min(abs(x-y),n-abs(x-y)));};
}
if(v[i].size()==1) continue;
for(int j=0;j<v[i].size();++j)
{
int x=v[i][j],y,w1,w2;
if(j!=0) y=v[i][j-1],w1=dp[y]+n-(x-y);
else y=v[i][v[i].size()-1],w1=dp[y]+y-x;
if(j!=v[i].size()-1) y=v[i][j+1],w2=dp[y]+n-(y-x);
else y=v[i][0],w2=dp[y]+x-y;
f[x]=min(w1,w2);
}
for(auto x:v[i]) dp[x]=f[x];
}
int ed=0;
for(auto x:v[m]) if(dp[x]<dp[ed]) ed=x;
cout<<dp[ed]<<'\n';
return 0;
}
至于输出路径？只需要简单地在记录最小值时记录是从哪儿推出的就行了...有些繁琐但只需要注意点细节就行了，所以不在此赘述。
完整代码：Submission #265943935 - Codeforces
标签：所有权,min,int,相邻,abs,CF612F,Circle,Simba,dp From： https://www.cnblogs.com/ilibilib/p/18535213