[NOI 2019]帰宅ルート(最短、スロープ最適化)

とうとうこの鬼の遊びを終わらせてしまった・・・
どうしてこんなにブスなのか・・・
(ついでにrouteseaに突っ込む)
最も短絡した状態は明らかである:(f[i])は、第(i)の線から降りる最小の代価を表す.
まず明らかにその式を分解しなければならない.直感はこれが傾き最適化であるべきだと教えてくれた.
\[f[i]=\min(f[j]+A(p_i-q_j)^2+B(p_i-q_j)+C)(x_i=y_j,p_i\ge q_j)\]\[f[i]=\min(f[j]+Ap_i^2-2Ap_iq_j+Aq_j^2+Bp_i-Bq_j+C)(x_i=y_j,p_i\ge q_j)\]\[f[i]=Ap_i^2+Bp_i+C+\min((-2Aq_j)\times p_i+(Aq_j^2-Bq_j+f[j]))(x_i=y_j,p_i\ge q_j)\]
後ろには明らかな傾き最適化がある.(明らかにシンクロナイズドゲームでSBが見えなかった)
しかし、具体的にはどうすればいいのでしょうか.私のコードは臭くて長いかもしれませんが、ここにあるかもしれません.
私のやり方は、線を(p)で並べ替えて、小さいものから大きいものまで列挙します.
始点の凸包に線を入れるたびに線を引くので、つける(qle)という線の(p)に注意します.小さい頃からこれを列挙するのは簡単だからです.
そして凸包に二分し、自分のこの線を終点の凸包の候補に加える.
しかし、私は料理が多すぎて、setメンテナンスバッグを手に入れたいだけなので、醜いです.
そして二分があるので、また隣の線の交点にセットして・・・
いずれにしても時間複雑度(O(mlogm)).

#include
using namespace std;
const int maxn=400040;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
    int x=0,f=0;char ch=getchar();
    while(ch'9') f|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
struct edge{
    int u,v,p,q,id;
    bool operatori.k;
        return b>i.b;
    }
};
struct point{
    double x;
    int k,b;
    bool operator in[maxn];
set hull[maxn];
set pt[maxn];
double interx(item i1,item i2){
    return i1.k==i2.k?1e10:1.0*(i2.b-i1.b)/(i1.k-i2.k);
}
void remove(int id,set::iterator it){
    set::iterator it1=it,it2=it;
    it2++;
    if(it1!=hull[id].begin()){
        it1--;
        pt[id].erase((point){interx(*it1,*it),it1->k,it1->b});
        it1++;
    }
    if(it2!=hull[id].end()) pt[id].erase((point){interx(*it,*it2),it->k,it->b});
    if(it1!=hull[id].begin() && it2!=hull[id].end()){
        it1--;
        pt[id].insert((point){interx(*it1,*it2),it1->k,it1->b});
    }
    hull[id].erase(it);
}
void insert(int id,item x){
    set::iterator it=hull[id].insert(x).first;
    set::iterator it1=it,it2=it;it2++;
    if(it1!=hull[id].begin()){
        it1--;
        if(it->k==it1->k) hull[id].erase(it1);
        else it1++;
    }
    if(it2!=hull[id].end()){
        if(it->k==it2->k) return void(hull[id].erase(it));
    }
    it1=it2=it=hull[id].find(x);it2++;
    if(it1!=hull[id].begin() && it2!=hull[id].end()){
        it1--;
        if(interx(x,*it1)>interx(x,*it2)) return void(hull[id].erase(x));
    }
    it=it1=it2=hull[id].find(x);it2++;
    if(it1!=hull[id].begin() && it2!=hull[id].end()){
        it1--;
        pt[id].erase((point){interx(*it1,*it2),it1->k,it1->b});
        it1++;
    }
    if(it1!=hull[id].begin()){
        it1--;
        pt[id].insert((point){interx(*it1,*it),it1->k,it1->b});
    }
    if(it2!=hull[id].end()) pt[id].insert((point){interx(*it,*it2),it->k,it->b});
    it=it1=hull[id].find(x);
    while(it1!=hull[id].begin()){
        it1--;
        if(it1==hull[id].begin()) break;
        it2=it1;it2--;
        if(interx(x,*it2)>interx(x,*it1)) remove(id,it1);
        else break;
        it=it1=hull[id].find(x);
    }
    it=it1=hull[id].find(x);it1++;
    while(it1!=hull[id].end()){
        it2=it1;it2++;
        if(it2==hull[id].end()) break;
        if(interx(x,*it2)q<=e[i].p){
            int q=in[e[i].u].begin()->q,id=in[e[i].u].begin()->id;
            insert(e[i].u,(item){-2*A*q,A*q*q-B*q+f[id]});
            in[e[i].u].erase(in[e[i].u].begin());
        }
        if(hull[e[i].u].empty()) continue;
        int p=e[i].p,k,b;
        set::iterator it=pt[e[i].u].lower_bound((point){e[i].p,-2e9,2e9});
        if(it==pt[e[i].u].end()){
            set::iterator it=hull[e[i].u].end();it--;
            k=it->k;b=it->b;
        }
        else k=it->k,b=it->b;
        f[e[i].id]=A*p*p+B*p+C+k*p+b;
        in[e[i].v].insert(e[i]);
        if(e[i].v==n) ans=min(ans,f[e[i].id]+e[i].q);
    }
    printf("%d
",ans);
}

転載先:https://www.cnblogs.com/1000Suns/p/11255037.html