【NOI2019】回家路线【无后效性dp状态设计】【斜率优化】

传送门

题意：给定$M$个班车，每个班车$p_i$时刻从$x_i$发车$q_i$到达$y_i$，等车$t$时间花费代价$A{t}^2+Bt+C$,在$t$时刻到达花费$t$的代价，求从$1$到$N$的最小花费。

$1\le N\le 100000,1\le M\le 200000$

显然是个dp

容易想到一个二维dp，第一维记当前位置，第二维记时间

由于数据范围很大，所以需要优化掉一维

仔细想想为什么需要两维？

因为位置是有后效性的，需要用时间节点来标记。

而时间是一去不复返的，是个天然的无后效性状态。

所以可以考虑按时间dp，先假设没有位置限制。

此题对时间唯一的限制是不能冲突，所以按照班车的时间段dp。

假设可以瞬间移动，不计最终代价，设坐上第$i$辆班车的最小代价是$f_i$

$$f_i=\underset{q_j\le p_i}{\min }\{f_j+A(p_i-q_j{)}^2+B(p_i-q_j)+C\}$$

盲猜斜率优化

假设决策$j,k$有$j<k$,$k$比$j$优

即

$$f_k+A(p_i-q_j{)}^2+B(p_i-q_j)+C\le f_j+A(p_i-q_j{)}^2+B(p_i-q_j)+C$$

$$f_k+A(p_i-q_j{)}^2+B(p_i-q_j)\le f_j+A(p_i-q_j{)}^2+B(p_i-q_j)$$

$$f_k+A{p}_i^2-2A{p}_i{q}_k+q_k^2+B{p}_i-B{q}_k\le f_j+A{p}_i^2-2A{p}_i{q}_j+q_j^2+B{p}_i-B{q}_j$$

$$f_k-2A{p}_i{q}_k+q_k^2-B{q}_k\le f_j-2A{p}_i{q}_j+q_j^2-B{q}_j$$

$$2A{p}_i+B\ge \frac{f_k+q_k^2-f_j-q_j^2}{q_k-q_j}$$

发现$p$和$q$分开了(其实不分开也能做的说)

所以可以把出发和到达拆开，分别排序，双指针维护

考虑位置限制

对于一个$p_i$,只有$y_j=x_i$的$q_j$会更新答案

所以可以用vector存$N$个凸壳

遇到出发在对应结点的凸壳上算出$f$。因为脑袋抽了写了个二分。

遇到到达在对应结点用之前的$f$更新凸壳

最后能到达$N$的算答案。

当时做的时候式子推反了，然后二分的时候凸壳算反了就负负得正A了……

我可能是个傻子

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> #include <vector> #define MAXN 200005 using namespace std; struct event{int idx,pos,tim;}st[MAXN],ed[MAXN]; inline bool cmp(const event& a,const event& b){return a.tim<b.tim;} int n,m,A,B,C; int f[MAXN]; inline int Y(const int& i){return f[ed[i].idx]+ed[i].tim*ed[i].tim;} inline int calc(const int& i,const int& j) {int d=st[i].tim-ed[j].tim;return f[ed[j].idx]+A*d*d+B*d+C; } vector<int> v[MAXN]; int vis[MAXN]; int main() {scanf("%d%d%d%d%d",&n,&m,&A,&B,&C);for (int i=1;i<=m;i++){int x,y,p,q;scanf("%d%d%d%d",&x,&y,&p,&q);st[i]=(event){i,x,p};ed[i]=(event){i,y,q};}memset(f,0x7f,sizeof(f));sort(st+1,st+m+1,cmp);sort(ed+1,ed+m+1,cmp);int now=0;for (int i=1;i<=m;i++){while (now<m&&ed[now+1].tim<=st[i].tim){++now;if (vis[ed[now].idx]) continue;vector<int>& cur=v[ed[now].pos];while (cur.size()>1&&(Y(now)-Y(cur[cur.size()-1]))*(ed[cur[cur.size()-1]].tim-ed[cur[cur.size()-2]].tim)<=((Y(cur[cur.size()-1])-Y(cur[cur.size()-2]))*(ed[now].tim-ed[cur[cur.size()-1]].tim))) cur.pop_back();cur.push_back(now);}if (st[i].pos==1) f[st[i].idx]=A*st[i].tim*st[i].tim+B*st[i].tim+C;else{vector<int>& cur=v[st[i].pos];if (cur.size()){int l=0,r=cur.size()-1,mid;while (l<r){mid=(l+r)>>1;if ((2*A*st[i].tim+B)*(ed[cur[mid+1]].tim-ed[cur[mid]].tim)<=Y(cur[mid+1])-Y(cur[mid])) r=mid;else l=mid+1;}f[st[i].idx]=calc(i,cur[l]);}else vis[st[i].idx]=true;}}int ans=f[0];for (int i=1;i<=m;i++) if (ed[i].pos==n) ans=min(ans,f[ed[i].idx]+ed[i].tim);printf("%d\n",ans);return 0; }

总结

以上是生活随笔为你收集整理的【NOI2019】回家路线【无后效性dp状态设计】【斜率优化】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。