解析

《論什么是合理的實現》

本題dp的斜率式子還是不難
惡心在其他地方
由于不能時光倒流，新點必須在q時間后再插入
因此我們開一個堆來按找q升序排列，算完一個點就塞到堆里，每次把當前可以插入的點一起彈出來插入
一個重要的技巧是只存儲火車的編號，就可以很陽間的使用宏定義
vector雖然不能popfront，但是可以把begin給erase掉
一定要記得判斷分母的符號！！！

代碼

#include<bits/stdc++.h> using namespace std; const int N=1e6+100; #define ll long long ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } int n,m; ll a,b,c,mx; struct node{ll u,v,p,q,id; }; bool cmp1(node a,node b){return a.p<b.p;} struct cmp2{bool operator ()(const node a,const node b){return a.q>b.q;} }; priority_queue<node,vector<node>,cmp2>pq; node o[N]; vector<int>que[N]; ll dp[N],res=2e18; #define X(ww) o[ww].q #define Y(ww) (dp[ww]+a*o[ww].q*o[ww].q-b*o[ww].q) signed main(){#ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);#endifn=read();m=read();a=read();b=read();c=read();for(int i=1;i<=m;i++){o[i]=(node){read(),read(),read(),read()};}sort(o+1,o+1+m,cmp1);o[0]=(node){0,1,0,0,0};pq.push(o[0]);for(int i=1;i<=m;i++){o[i].id=i;while(pq.size()&&pq.top().q<=o[i].p){node now=pq.top();pq.pop();int v=now.v,id=now.id;//printf("v=%d\n",v);while(que[v].size()>=2){int oo=que[v].size(),x=que[v][oo-2],y=que[v][oo-1];if((X(id)-X(y))*(X(y)-X(x))>=0){if((Y(y)-Y(x))*(X(id)-X(y))>=(Y(id)-Y(y))*(X(y)-X(x))) que[v].pop_back();else break;}else{if((Y(y)-Y(x))*(X(id)-X(y))<=(Y(id)-Y(y))*(X(y)-X(x))) que[v].pop_back();else break;}}que[v].push_back(now.id);}node now=o[i];int u=now.u,v=now.v,p=now.p,q=now.q;while(que[u].size()>=2){int x=que[u][0],y=que[u][1];ll k=2*a*now.p;//printf("(%lld %lld %lld) (%lld %lld %lld) k=%lld\n",o[x].id,X(x),Y(x),o[y].id,X(y),Y(y),k);if(X(y)-X(x)>=0){if((Y(y)-Y(x))<=k*(X(y)-X(x))) que[u].erase(que[u].begin());else break;}else{if((Y(y)-Y(x))>=k*(X(y)-X(x))) que[u].erase(que[u].begin());else break;}}//printf("i=%d u=%lld v=%lld p=%lld q=%lld siz=%d\n",i,o[i].u,o[i].v,o[i].p,o[i].q,(int)que[v].size());if(que[u].size()){int j=que[u][0];ll d=o[i].p-o[j].q;dp[i]=dp[j]+a*d*d+b*d+c;//printf("i=%d j=%d dp=%lld\n",i,j,dp[i]);if(v==n) res=min(res,dp[i]+o[i].q);pq.push(o[i]);}}printf("%lld\n",res);return 0; }

總結

以上是生活随笔為你收集整理的洛谷P6302：回家路线（斜率优化）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。