题解 CF612F 【Simba on the Circle】
xtx1092515503
2020-12-21 19:27:40
挺烦人的一道DP题。
------------
首先，本题的阶段是很容易设想出来的：因为要求“输出的东西不降”，所以必须先将所有 $1$ 输出，然后是所有 $2$，然后是所有 $3$……在不同的数字间，转移是有序的；但是在同一数字间，转移就可能不太trival了。
首先先设出DP状态。设 $f_i$ 表示若 $i$ 是所有值为 $a_i$ 的位置中第一个被输出的，此时所移动的最短距离，再设 $g_i$ 表示若 $i$ 是所有值为 $a_i$ 的位置中最后一个被输出的，此时所移动的最短距离。则答案即为
$$\min\limits_{a_i\text{ is maximum}}g_i$$
先考虑不同数字间的转移。假如 $j,k$ 分别是一个小一点的数和一个大一点的数，则有
$$g_j+\min\Big\{(k-j)\bmod n,(j-k)\bmod n\Big\}\rightarrow f_k$$
因为 $n$ 只有 $2000$，所以暴力枚举这样的 $(j,k)$ 进行转移即可。
然后再考虑相同数字间的转移。我们可以大胆猜测，假如我们从一个 $f_j$ 转移到 $g_k$，则必定是先顺时针/逆时针走到 $k$ 的前一个数，然后再掉头一路走到 $k$。
具体式子很长，直接看代码即可。明显这里仍然可以 $n^2$ 枚举转移。
比较恶心的是输出，不同数字间的转移还好，烦人的是相同数字间的转移。按照上文所述的实际意义进行转移即可，详情见代码。
总时间复杂度 $O(n^2)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,p,a[2010],f[2010],g[2010],F[2010],G[2010],res=0x3f3f3f3f;//f:the minimal starting from i; g:the minimal ending at i
vector<int>v[2010],u;
stack<int>s;
int main(){
scanf("%d%d",&n,&p),p--,memset(f,0x3f,sizeof(f)),memset(g,0x3f,sizeof(g));
for(int i=0;i<n;i++)scanf("%d",&a[i]),u.push_back(a[i]);
sort(u.begin(),u.end()),u.resize(m=unique(u.begin(),u.end())-u.begin());
for(int i=0;i<n;i++)v[a[i]=lower_bound(u.begin(),u.end(),a[i])-u.begin()+1].push_back(i);
// for(int i=0;i<n;i++)printf("%d ",a[i]);puts("");
// for(int i=1;i<=m;i++){for(auto j:v[i])printf("%d ",j);puts("");}
for(auto i:v[1])f[i]=min((i+n-p)%n,(p+n-i)%n),F[i]=-1;
for(int i=1;i<=m;i++){
int len=v[i].size();
for(int j=0;j<len;j++)for(int k=0;k<len;k++){
if(j==k)continue;
int J=v[i][j],K=v[i][k];
int A=(v[i][(k+len-1)%len]+n-J)%n*2+(J+n-K)%n;
int B=(J+n-v[i][(k+1)%len])%n*2+(K+n-J)%n;
if(g[K]>f[J]+min(A,B))g[K]=f[J]+min(A,B),G[K]=J;
}
if(len==1)g[v[i][0]]=f[v[i][0]],G[v[i][0]]=v[i][0];
if(i==m)continue;
for(auto j:v[i])for(auto k:v[i+1])if(f[k]>g[j]+min((k+n-j)%n,(j+n-k)%n))f[k]=g[j]+min((k+n-j)%n,(j+n-k)%n),F[k]=j;
}
// for(int i=0;i<n;i++)printf("%d ",f[i]);puts("");
// for(int i=0;i<n;i++)printf("%d ",g[i]);puts("");
for(auto i:v[m])res=min(res,g[i]);
printf("%d\n",res);
for(auto K:v[m]){
if(g[K]!=res)continue;
for(int i=m;i;i--){
int len=v[i].size();
int J=G[K];
int j=lower_bound(v[i].begin(),v[i].end(),J)-v[i].begin(),k=lower_bound(v[i].begin(),v[i].end(),K)-v[i].begin();
int A=(v[i][(k+len-1)%len]+n-J)%n*2+(J+n-K)%n;
int B=(J+n-v[i][(k+1)%len])%n*2+(K+n-J)%n;
if(len>1){
if(A<B){
for(int l=k;(l+1)%len!=j;(++l)%=len)s.push(-(v[i][(l+1)%len]+n-v[i][l])%n);
s.push(-(v[i][(k+len-1)%len]+n-v[i][(j+len-1)%len])%n);
for(int l=(k+len-1)%len;l!=j;(l+=len-1)%=len)s.push((v[i][l]+n-v[i][(l+len-1)%len])%n);
}else{
for(int l=k;(l+len-1)%len!=j;(l+=len-1)%=len)s.push((v[i][l]+n-v[i][(l+len-1)%len])%n);
s.push((v[i][(j+1)%len]+n-v[i][(k+1)%len])%n);
for(int l=(k+1)%len;l!=j;(++l)%=len)s.push(-(v[i][(l+1)%len]+n-v[i][l])%n);
}
}
A=J,B=F[J];
if(B==-1)B=p;
s.push((A+n-B)%n<(B+n-A)%n?(A+n-B)%n:-(B+n-A)%n);
K=B;
}
break;
}
// auto S=s;while(!S.empty())printf("%d ",(p+=S.top()+n)%n),S.pop();puts("");
while(!s.empty())printf("%c%d\n",(s.top()>=0?'+':'-'),abs(s.top())),s.pop();
return 0;
}
```