codeforces gym 102012 C - Rikka with Consistency

题意：有两个人沿着一条折线走来走去，一开始两个人的位置分别是$(0,0)$和$(n,0)$要求行走的过程当中两个人的高度必须**完 全 一 致**,最小化将两个人交换位置的路程和 那么我们发现可以搞个最短路模型出来，我们可以将状态$(p,q,h)$看成一个点，这个状态表示第一个人在$[p,p+1]$这段折线上,第二个人在$[q,q+1]$这段折线上，两个人的高度同时为$h$ 那么我们会发现根据状态定义我们大部分时候可以确定这两个人在什么位置上，但是有一个特例就是如果$[p,p+1]$或者$[q,q+1]$这一段是平的我们的人就有两个可能的位置，这种情况下为了避免歧义我们强行钦定人会在纵坐标较小的点上 根据状态定义我们会发现有些不同的状态会描述同一个点，此时我们把这些状态的编号设成一致的即可 那么我们连边就非常简易了,无非就是高度+1和高度-1两种不同的转移方式，还有就是在平的折线上向前走一步和向后走一步这些转移，直接练完边之后跑最短路即可 注意一点如果$h(n)$和$h(n-1)$相同，按照状态定义我们会求出$(0,n,0)$到$(n,0,0)$的最短路，但是此时我们求出的其实是$(0,n-1,0)$到$(n-1,0,0)$的最短路，要把答案+2才是正确答案 复杂度$O(Tn^2 logn \Sigma h(i))$可以通过本题 上代码~ ```C #include<cstdio> #include<algorithm> #include<queue> #include<cmath> using namespace std;const int N=5e6+10;const int M=60;typedef double db;const db inf=(db)(1LL<<40); int v[N];int x[N];int al[N];db val[N];db dis[N];bool book[N];int S;int T;int ctt;int ct; int n;int tr[M][M][M];int h[N]; struct data { int u;db dis; friend bool operator <(data a,data b){return a.dis>b.dis;} };priority_queue <data> pq; inline void add(int u,int V,db va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;} inline void dij()//dijkstra { for(int i=1;i<=ctt;i++)dis[i]=inf;dis[S]=0; for(int i=1;i<=ctt;i++)book[i]=false;pq.push((data){S,0}); while(!pq.empty()) { data nw=pq.top();pq.pop();if(book[nw.u])continue;book[nw.u]=true; for(int i=al[nw.u];i;i=x[i]) if(dis[v[i]]>nw.dis+val[i]) dis[v[i]]=nw.dis+val[i],pq.push((data){v[i],dis[v[i]]}); } } inline int mabs(int x,int y){return (x>y)?x-y:y-x;} inline void solve()//建图 { scanf("%d",&n);n++;for(int i=1;i<=n;i++)scanf("%d",&h[i]); for(int i=1;i<n;i++) for(int j=1;j<n;j++) { int l1=min(h[i],h[i+1]);int r1=max(h[i],h[i+1]); int l2=min(h[j],h[j+1]);int r2=max(h[j],h[j+1]); for(int k=max(l1,l2);k<=min(r1,r2);k++)tr[i][j][k]=++ctt; } for(int i=1;i+1<n;i++) for(int j=1;j<n;j++) if(tr[i][j][h[i+1]]&&tr[i+1][j][h[i+1]]) { if(h[i]==h[i+1])continue; int mi=min(tr[i][j][h[i+1]],tr[i+1][j][h[i+1]]); tr[i][j][h[i+1]]=tr[i+1][j][h[i+1]]=mi; } for(int j=1;j+1<n;j++) for(int i=1;i<n;i++) if(tr[i][j][h[j+1]]&&tr[i][j+1][h[j+1]]) { if(h[j]==h[j+1])continue; int mi=min(tr[i][j][h[j+1]],tr[i][j+1][h[j+1]]); tr[i][j][h[j+1]]=tr[i][j+1][h[j+1]]=mi; } for(int i=1;i+1<n;i++) for(int j=1;j<n;j++) { int u=tr[i][j][h[i+1]];int v=tr[i+1][j][h[i+1]]; if(u&&v&&h[i]==h[i+1])add(u,v,1),add(v,u,1); } for(int j=1;j+1<n;j++) for(int i=1;i<n;i++) { int u=tr[i][j][h[j+1]];int v=tr[i][j+1][h[j+1]]; if(u&&v&&h[j]==h[j+1])add(u,v,1),add(v,u,1); } for(int i=1;i<n;i++) for(int j=1;j<n;j++) { int le1=mabs(h[i],h[i+1]);int le2=mabs(h[j],h[j+1]); db va=sqrt(1+le1*le1)/(db)le1+sqrt(1+le2*le2)/(db)le2; for(int k=0;k<50;k++) { int u=tr[i][j][k];int v=tr[i][j][k+1]; if(u&&v)add(u,v,va),add(v,u,va); } }S=tr[1][n-1][0];T=tr[n-1][1][0]; dij();printf("%.15lf\n",dis[T]+(h[n]==h[n-1])*2);//特判 } inline void clear() { for(int i=1;i<n;i++) for(int j=1;j<n;j++) { int l1=min(h[i],h[i+1]);int r1=max(h[i],h[i+1]); int l2=min(h[j],h[j+1]);int r2=max(h[j],h[j+1]); for(int k=max(l1,l2);k<=min(r1,r2);k++)tr[i][j][k]=0; } for(int i=1;i<=ctt;i++)al[i]=0;ct=0;ctt=0; } int main() {int cas;scanf("%d",&cas);for(int z=1;z<=cas;z++)solve(),clear();return 0;}//拜拜程序~ ```