题解 CF1503C【Travelling Salesman Problem】

· · 题解

CF1503C 题解

赛后，看了一眼 Editorial 的转化，但没想到后面比较妙的计算方式。

考虑将 \max(c_i,a_j-a_i) 转化成 c_i+\max(0,a_j-a_i-c_i)。由于每个点都会经过恰好一次，所以答案最小就是 \sum c_i，然后只需要处理 \max 即可。

将所有城市按照 a_i 升序排序，并将它们重编号为 1\sim n。这时候答案可以表示为 1\to n \to 1 且每个点恰好经过一次的最小花费。

可以发现，n\to 1 的代价恒为 0。于是只需要考虑 1\to n 的最小代价，然后从 n\to 1 的路径上再覆盖未被经过的点即可。

设 f_i 为 i\to n 的最小代价。首先二分求出 k，表示最小的满足 a_k-a_i-c_i>0 的位置。然后 f_i=\min\left(\min(f_{i+1},f_{i+2},\dots , f_{k-1}),\min(f_{k}+a_k,\dots,f_{n}+a_n)-a_i-c_i\right)。

前半部分用线段树维护，后半部分开个数组维护即可。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <utility>
#include <algorithm>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T>
inline bool chkmax(T &i,const T&j){return i<j?(i=j,1):0;}
template<typename T>
inline bool chkmin(T &i,const T&j){return i>j?(i=j,1):0;}
template<typename T> void Read(T &x){
    快读略;
}
typedef long long ll;
const int N=1e5+5;const ll Infll=0x3f3f3f3f3f3f3f3f;
typedef pair<ll,ll> Pll;
int n;Pll a[N];ll min2[N],f[N];
#define ls(xx) ((xx)<<1)
#define rs(xx) ((xx)<<1|1)
struct Node{Node():v(Infll){}ll v;}t[N<<2];
void Pushup(int p){t[p].v=min(t[ls(p)].v,t[rs(p)].v);}
void Modify(int p,int L,int R,int x,ll k){
    if(L==R){
        t[p].v=k;return;
    }int mid=(L+R)>>1;
    if(x<=mid) Modify(ls(p),L,mid,x,k);
    else Modify(rs(p),mid+1,R,x,k);
    Pushup(p);
}
ll QMin(int p,int L,int R,int l,int r){
    if(l<=L&&R<=r) return t[p].v;
    int mid=(L+R)>>1;ll res=Infll;
    if(l<=mid) chkmin(res,QMin(ls(p),L,mid,l,r));
    if(r>mid) chkmin(res,QMin(rs(p),mid+1,R,l,r));
    return res;
}
int main(){
    Read(n);
    For(i,1,n){
        Read(a[i].first);Read(a[i].second);
    }
    sort(a+1,a+n+1);
    min2[n+1]=Infll;
    min2[n]=a[n].first;Modify(1,1,n,n,0);
    Dec(i,n-1,1){
        int k=upper_bound(a+i+1,a+n+1,make_pair(a[i].first+a[i].second,Infll))-a;
        f[i]=min(QMin(1,1,n,i,k-1),min2[k]-a[i].first-a[i].second);
        Modify(1,1,n,i,f[i]);min2[i]=min(min2[i+1],f[i]+a[i].first);
    }
    ll ans=f[1];
    For(i,1,n) ans+=a[i].second;
    printf("%lld\n",ans);
    return 0;
}