luogu P5468 [NOI2019]回家路线 (斜率优化、DP)

题目链接: (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("%lldn",ans); return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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("%lldn",ans);
    return 0;
}