[NOI2019]回家路线

一、题目

点此看题

二、解法

首先可以用暴力$dp$艹过去，设$dp[i][j]$为到了$i$点的时间是$j$的最小花费，由于时间是单向流逝的，我们可以先把边按出发时间排序，用边转移，枚举到达出发点的时间$j$： $$dp[y[i]][q[i]]=dp[x[i]][j]+cost(p[i]-j)$$但是人总要追求正解，设$dp[i]$为正好走过第$i$条边的最小花费，转移枚举上一次走过的边$j$，转移需要满足条件：$q_j\le p_i,y[j]=x[i]$，方程式如下： $$dp[i]=dp[j]+A(p[i]-q[j]{)}^2+B(p[i]-q[j])+C$$这种平方转移好像能推斜率式，设转移点$j>k$，且$j$决策点优（给结论）： $$\frac{dp[j]+Aq[j{]}^2-Bq[j]-dp[k]-q[k{]}^2+Bq[k]}{q[j]-q[k]}<2Ap[i]$$画个图可以发现斜率是单调递增的，但是现在的转移顺序问题还是有些蛋疼，观察我们转移需要的两个条件，我们可以先满足第二个条件，也就是维护$n$个凸包，询问的时候到对应的凸包里面查询。那第一个条件怎么办？我们转移的时候先枚举边的出发时间，插入凸包的时候只插入结束时间不超过它的，这样凸包里的东西就满足第一个条件了。

时间复杂度$O(m)$，凸包需要$\mathtt{v}\mathtt{e}\mathtt{c}\mathtt{t}\mathtt{o}\mathtt{r}$

#include <cstdio> #include <vector> #include <queue> using namespace std; const int M = 200005; int read() { int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int n,m,ans,A,B,C,x[M],y[M],p[M],q[M],h[M],t[M],dp[M]; vector<int> Q[M],a[M];queue<int> b[M]; int up(int j,int k) { return dp[j]+A*q[j]*q[j]-B*q[j]-dp[k]-A*q[k]*q[k]+B*q[k]; } int down(int j,int k) { return q[j]-q[k]; } void ins(int u,int i)//在u凸包插入i { while(h[u]<t[u] && 1ll*up(Q[u][t[u]],Q[u][t[u]-1])*down(i,Q[u][t[u]])>=1ll*up(i,Q[u][t[u]])*down(Q[u][t[u]],Q[u][t[u]-1])) t[u]--; while(Q[u].size()<t[u]+3) Q[u].push_back(0); Q[u][++t[u]]=i; } void fuck(int u,int i)//在u凸包中把不满足i的艹出去 { while(h[u]<t[u] && 1ll*up(Q[u][h[u]+1],Q[u][h[u]])<=2ll*A*p[i]*down(Q[u][h[u]+1],Q[u][h[u]])) h[u]++; } signed main() { n=read();m=read();A=read();B=read();C=read(); for(int i=1;i<=m;i++) { x[i]=read();y[i]=read(); p[i]=read();q[i]=read(); a[p[i]].push_back(i); }ans=1e18; for(int i=2;i<=n;i++) t[i]=-1; Q[1].push_back(0); for(int T=0;T<=1000;T++) { while(!b[T].empty()) { int u=b[T].front();b[T].pop(); ins(y[u],u); } for(int i=0;i<a[T].size();i++) { int u=a[T][i]; if(h[x[u]]>t[x[u]]) continue; fuck(x[u],u); int j=Q[x[u]][h[x[u]]]; dp[u]=dp[j]+A*(p[u]-q[j])*(p[u]-q[j])+B*(p[u]-q[j])+C; b[q[u]].push(u); if(y[u]==n) ans=min(ans,dp[u]+q[u]); } } printf("%d\n",ans); } /* dp[i]=min(dp[j]+A(pi-qj)^2+B(pi-qj)+C) x[i]=y[j] j在后，j优 dp[j]+A(pi-qj)^2+B(pi-qj)<dp[k]+A(pi-qk)^2+B(pi-qk) dp[j]+A(-2piqj+qj^2)-Bqj<dp[k]+A(-2piqk+qk^2)-Bqk dp[j]+Aqj^2-Bqj-dp[k]-qk^2+Bqk<2Api(qj-qk) */