【DP】CodeForces612F Simba on the Circle

题意：

给出一个环状的序列，每个位置有一个值$a_i$，初始位置为s，现在要求从小到大依次遍历每个点。要求总步数尽可能小。
序列长度$N\leq 2000$

---

分析：

这是一道代码题。。。。
所谓代码题，就是思路异常简单，但实现起来细节暴多的题。。。。

第一问：

其实大致方法很简单，定义$dp[i]$表示将所有$a_j\leq a_i$的位置都遍历后，停在$a_i$位置的最小步数（注：必须满足在遍历$a_j=a_i$这一层时，$i$位置只能经过一次）。

转移就非常暴力了。
我们对$a_i$相同的在同一次处理，定义为$S$。
定理序列$G$表示$a_{S_i}$为严格小于$a_i$的最大的数组成的序列（说白了就是上一次处理的那些位置）

所以$dp_i=min\{dp_{G_j}+从G_j出发遍历所有S_i中的点最终到达i的最小步数\}$
我们可以O(n)地枚举$G_j$，然后用O(1)的复杂度求出后面那一坨。。。（总复杂度$O(n^2)$）

所以，恶心的就是如何用O(1)的复杂度求出后面那一坨。。。。

首先要引入2个辅助函数
$len(u,v)$表示从u到v的最小步数。
$len(u,v,k)$表示从u出发，不经过k到达v的步数。
$prep$表示在S中i左边的第一个位置$(prep=(i-1+|s|)mod|s|)$
$lasp$表示在S中i右边的第一个位置$(lasp=(i+1)mod |s|)$
由于我们定义的$dp_i$的特殊要求（在当前层中，$i$位置只经过一次）

所以我们可以分为这么3种情况：

1、

这种情况（好吧其实是2种）满足$prep=lasp$，
代价可以表示为：$len(G_j,S_{prep})+len(S_{prep},S_i)$

2、

这种情况满足$(l->S_{prep},r->S_{lasp},x->G_j)$

说白了，就是$G_j$被包在$S_{prep},S_i$或$S_i,S_{lasp}$之间。

这种情况下我们肯定要从$G_j$出发，绕外面所有$S$中的点一圈，再从另一侧回来

这部分可以等价地表示为：$n-len(G_j,S_i,S_{prep})(其实=n-len(G_j,S_i,S_{lasp}))$

3、

这部分就相对常规一些，公式也相对复杂一些：

我们可以走基佬紫和原谅绿两种颜色表示的路径。

取个min就可以了

所以表示为：

$$len(G_j,S_{prep},S_i)+len(G_j,S_{lasp},S_i) +\space min\{len(G_j,S_{prep},S_i)+len(S_{lasp,S_i}),len(G_j,S_{lasp},S_i)+len(S_{prep},S_i) \}$$
min里面前者表示基佬紫走法
后者表示原谅绿走法

然后。。。我们就可以得到第一问的答案了。。

第二问

和所有DP求方案的题一样，这道题也需要记录转移路径。

这里还要借助一个辅助函数$len1(u,v)$表示从u走到v的小步数（含正负）
然后还是分为上面3类讨论：

对于第1类：

走法无非是

应该很简单我就直接粘代码了。

对于第2类：

上面已经把走法解释过了，所以我还是直接上代码吧：

对于第3类：

这里的具体走法稍微有点巧妙。

首先还是判断一下哪条路代价最小，然后走小的那一边。

这里我们可以直接从$G_j$走到$S_{prep}$，再以递减的顺序走完$S$中的点回到$S_i$

或从$G_j$走到$S_{lasp}$，以递增的顺序走完$S$中的点回到$S_i$

实在还有不懂的就去看代码吧。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 2010
#define INF 0x3f3f3f3f
using namespace std;
int n,s;
int dp[MAXN],com[MAXN],cnt;
vector<int> las[MAXN],now;
pair<int,int> a[MAXN];
int len(int x,int y){if(x>y)swap(x,y);return min(y-x,x+n-y);
}
int len(int x,int y,int blo){if(x>y)swap(x,y);if(blo==x||blo==y)return len(x,y);if(x<blo&&blo<y)return x+n-y;if(blo<x||blo>y)return y-x;
}
bool checkin(int x,int l,int r){if(l<r)return x>=l&&x<=r;elsereturn x<=r||x>=l;
}
void solve(){int m=now.size();for(int i=0;i<m;i++)for(int j=0;j<las[cnt].size();j++){int prep=now[(i-1+m)%m];int lasp=now[(i+1+m)%m];int u=now[i];int v=las[cnt][j];int val=0;if(prep==lasp){val=len(v,prep)+len(prep,u);//PF("[1]");}else if(checkin(v,prep,lasp)){val=n-len(u,v,prep);//PF("[2]");}elseval=len(v,prep,u)+len(v,lasp,u)+min(len(v,lasp,u)+len(prep,u),len(v,prep,u)+len(lasp,u));//PF("{%d %d}\n",u,val);if(cnt!=0)val+=dp[las[cnt][j]];if(val<dp[now[i]]){dp[now[i]]=val;com[now[i]]=j;  }}cnt++;for(int i=0;i<m;i++)las[cnt].push_back(now[i]);now.clear();
}
vector<int> print;
int len1(int x,int y){//PF("{%d %d}\n",x,y);int lenx=len(x,y);if((x+lenx-1)%n+1==y)return lenx;elsereturn -lenx;
}
void get_ans(int x,int tim){if(tim!=1)get_ans(com[las[tim][x]],tim-1);int m=las[tim].size();int prep=las[tim][(x-1+m)%m];int lasp=las[tim][(x+1)%m];int u=las[tim][x];int v=las[tim-1][com[u]];int val=0;if(prep==lasp){print.push_back(len1(v,prep));if(prep!=u)print.push_back(len1(prep,u));}else if(checkin(v,prep,lasp)){if(checkin(v,prep,u)){print.push_back(len1(v,prep));for(int j=(x-1+m)%m;j!=x;j=(j-1+m)%m)print.push_back(len1(las[tim][j],las[tim][(j-1+m)%m]));}else{print.push_back(len1(v,lasp));for(int j=(x+1)%m;j!=x;j=(j+1)%m)print.push_back(len1(las[tim][j],las[tim][(j+1)%m]));}}else{if(len(v,lasp,u)+len(prep,u)<len(v,prep,u)+len(lasp,u)){print.push_back(len1(v,lasp));for(int j=(x+1)%m;j!=x;j=(j+1)%m)print.push_back(len1(las[tim][j],las[tim][(j+1)%m]));}else{print.push_back(len1(v,prep));for(int j=(x-1+m)%m;j!=x;j=(j-1+m)%m)print.push_back(len1(las[tim][j],las[tim][(j-1+m)%m]));}}//PF("{%d %d %d}\n",u,tim,print.size());
}
int main(){memset(dp,INF,sizeof dp);SF("%d%d",&n,&s);for(int i=1;i<=n;i++){SF("%d",&a[i].first);a[i].second=i;}sort(a+1,a+1+n);las[0].push_back(s);now.push_back(a[1].second);for(int i=2;i<=n;i++){if(a[i].first!=a[i-1].first){solve();}now.push_back(a[i].second);}solve();/*for(int i=0;i<=cnt;i++){for(int j=0;j<las[i].size();j++)PF("{%d %d} ",las[i][j],dp[las[i][j]]);PF("\n");}*/int minid=0,minv=INF;for(int i=0;i<las[cnt].size();i++)if(dp[las[cnt][i]]<minv){minid=i;minv=dp[las[cnt][minid]];   }PF("%d\n",minv);get_ans(minid,cnt);for(int i=0;i<print.size();i++){if(print[i]>=0)PF("+%d\n",print[i]);elsePF("%d\n",print[i]);}
}