題目鏈接: (luogu) https://www.luogu.org/problemnew/show/P5468

題解: 爆long long毀一生

我太菜了，這題這么簡單考場上居然沒想到正解……

設\(dp[i]\)表示最后一步是坐\(i\)這輛車，一共花在等待上的煩躁值(不包括最終時間)為\(f[i]\).

然后容易發現這個轉移是個DAG。(我在考場上居然以為有環，于是直接放棄……)

轉移方程\(dp[i]=\min_{j|y[j]=x[i]}dp[j]+A(x_i-x_j)^2+B(x_i-x_j)+C\)

然后這東西顯然可以斜率優化，按時間順序枚舉每個\(i\), 對于一個\(i\)的開始我們根據\(x[i]\)求出\(dp[i]\), 對于一個\(i\)的結束我們用\(dp[i]\)去更新\(y[i]\). 然后顯然這個東西可以斜率優化，那么就對每個點\(i\)維護凸殼即可。

一定注意不要爆long long！我的\(\inf\)開到了\(10^{11}\), 所以必須保證不能把\(\inf\)加入到隊列里，否則斜率優化比較的時候兩個相乘必爆ll.

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #include<vector> #include<algorithm> #define llong long long using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int N = 1e5; const int M = 2e5; const int C = 1000; const llong INF = 100000000000ll; struct Point {llong x,y;Point() {}Point(llong _x,llong _y) {x = _x,y = _y;} }; struct Element {int u,v; llong x,y; } a[M+3]; vector<int> sid[C+3],tid[C+3]; vector<int> que[M+3]; int hd[M+3]; llong dp[M+3]; int n,m; llong arga,argb,argc;llong calcy(llong x) {return dp[x]+arga*a[x].y*a[x].y-argb*a[x].y;} llong calcx(llong x) {return 2ll*arga*a[x].y;} int cmp_slope(int x,int y,int z) {llong xx = calcx(x),xy = calcy(x),yx = calcx(y),yy = calcy(y),zx = calcx(z),zy = calcy(z);return (yy-xy)*(zx-yx)>(zy-yy)*(yx-xx) ? 1 : -1; } llong calcdp(int x,llong y) {return dp[x]+arga*(y-a[x].y)*(y-a[x].y)+argb*(y-a[x].y)+argc;}int main() {scanf("%d%d%lld%lld%lld",&n,&m,&arga,&argb,&argc); int mx = 0;for(int i=1; i<=m; i++){scanf("%d%d%lld%lld",&a[i].u,&a[i].v,&a[i].x,&a[i].y);sid[a[i].x].push_back(i); mx = max(mx,(int)a[i].y);}que[1].push_back(0);llong ans = INF;dp[1] = 0ll; for(int i=2; i<=m; i++) dp[i] = INF;for(int i=0; i<=mx; i++){for(int j=0; j<tid[i].size(); j++){int x = tid[i][j],v = a[x].v; //x: 邊的編號 v: 終點的編號 while(hd[v]+1<que[v].size() && cmp_slope(que[v][que[v].size()-2],que[v][que[v].size()-1],x)>=0) {que[v].pop_back();}que[v].push_back(x);}for(int j=0; j<sid[i].size(); j++){int x = sid[i][j],u = a[x].u; //x: 邊的編號 u: 起點的編號if(que[u].size()==0) continue; //注意特判! while(hd[u]+1<que[u].size() && calcdp(que[u][hd[u]],i)>=calcdp(que[u][hd[u]+1],i)) {hd[u]++;}dp[x] = calcdp(que[u][hd[u]],i);if(a[x].v==n) {ans = min(ans,dp[x]+a[x].y);}tid[a[x].y].push_back(x); //如果讀入時把所有y全都放進去，那么會導致隊列中出現inf而爆long long.}}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的luogu P5468 [NOI2019]回家路线 (斜率优化、DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

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