NOI真题解析(191)

赵思铭 · 2022-08-06 15:34:32 · 个人记录

回家路线，本题为DP，O(n^2)为70分，想到斜率优化O(nlog(n)),(排序为瓶颈)可以过。是一道代码量大思维量小的题

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
const int inf=0x3f3f3f3f3f3f3f3fll;
int n,m,A,B,C;
struct Edge {
    int u,v,p,q;
    bool operator<(const Edge &r)const {
        return p<r.p;
    }
}a[N]={(Edge){1,1,0,0}};
int f[N],cnt[N];
vector<int> Q[N],b[N];
//b[i]表示流入b[i]的点按照q增加的次序
bool cmp(int i,int j) {return a[i].q<a[j].q;}
void calc(int i,int j) {
    int x=a[i].p-a[j].q;
    f[i]=f[j]+A*x*x+B*x+C;
}
int ans=inf;
int X(int j) {return a[j].q;}
int Y(int j) {return A*a[j].q*a[j].q+f[j]-B*a[j].q;}
int k(int i) {return 2*A*a[i].p;}
double slope(int i,int j) {
    int dy=Y(j)-Y(i),dx=X(j)-X(i);
    if(dx==0) return dy>0?inf:-inf;
    return 1.0*dy/dx;
}
signed main() {
    cin>>n>>m>>A>>B>>C;
    for(int i=1;i<=m;i++) {
        cin>>a[i].u>>a[i].v>>a[i].p>>a[i].q;
    }
    sort(a,a+m+1);
    for(int i=0;i<=m;i++) {
        b[a[i].v].push_back(i);
    }
    for(int i=1;i<=n;i++) 
        sort(b[i].begin(),b[i].end(),cmp);
    for(int i=1;i<=m;i++) {
        int u=a[i].u;
        while(cnt[u]<(int)b[u].size()) {
            if(a[b[u][cnt[u]]].q<=a[i].p) {
                while(Q[u].size()>=2) {
                    int t=Q[u].size()-1;
                    if(slope(Q[u][t-1],Q[u][t])
                    <slope(Q[u][t],b[u][cnt[u]]))
                    break;
                    Q[u].pop_back();
                }
                Q[u].push_back(b[u][cnt[u]]);
                cnt[u]++;
            }
            else break;
        }
        int L=0,R=(int)Q[u].size()-2;
        while(L<=R) {
            int mid=(L+R)>>1;
            if(k(i)>slope(Q[u][mid],Q[u][mid+1])) 
                L=mid+1;
            else R=mid-1;
        }
        if(Q[u].size()) calc(i,Q[u][L]);
        else f[i]=inf;
    }
    for(int i=1;i<=m;i++)
        if(a[i].v==n)
            ans=min(ans,f[i]+a[i].q);
    cout<<ans<<endl;
    return 0;
}