题解 下楼

Find_Yourself · 2023-06-01 21:41:44 · 题解

不难推理出当初始绳长为 len，需要下降的距离为 d，并且满足 d\le len<2d 时，最优的环套法可以只损失 2d-len 长度的绳子，留下 2(len-d) 的绳子。

当 2d\le len 时存在一种不损耗绳长的方法可以下到下一根钢管，即把整根绳子系成一个环，到达下面再剪断。

正文：

线段树优化 DP。

我们先将所有钢管按高度从大到小排序，如果高度相同则按权值从小到大排序。

然后将权值离散化，对于相同的 v，给 h 更大的赋更小的值。

考虑从低往高 DP。

定义 f_i 表示最初站在 i 号钢管，至少需要多长的绳子才能下到地面。

转移方程如下：

开两棵线段树，第一棵 t_1 维护 \min(f_j)(h_j+\frac{f_j}{2}\ge h_i)，第二棵 t_2 维护 \min(-h_j+\frac{f_j}{2})(h_j+\frac{f_j}{2}<h_i)，每次分别在两棵线段树上查询 [v_i+1,n] 内的最小值，记为 m_1,m_2。那么 f_{i}=\min(m_1,m_2+h_i)。

容易发现，一根钢管的贡献是有范围的。

对于钢管 j，我们二分出离它最远的 i，满足 h_i\le h_j+\frac{f_j}{2}，那么 [i,j) 这些位置都可以通过第一种转移被 f_j 贡献到，[1,i) 这些位置可以通过第二种转移被 h_i-h_j+\frac{f_j}{2} 贡献到。

具体的，我们假设二分到的位置为 w，那么在 w-1 处标记编号 j，遍历到这里时，将 t_1 对应位置改为 \inf，t_2 对应位置改为 -h_j+\frac{f_j}{2}，更新一下线段树即可。

这里之所以可以通过赋值 \inf 来撤销，是因为离散化后已经保证 v_i 互不相同了。

注意，由于 h 在 10^{18} 级别，如果用 double 会爆精度并喜提 0 分，所以要用 long double。

如果你还不放心，可以在每次除以 2 后向上取整，至于为什么对，这里有具体证明。

我们之所以不考虑正着推（从上往下），是因为多一个二分带来的 \log，而且转移时分三段，写起来极其麻烦。

综上，复杂度 O(n\log n)，代码很短。

code:

#include<bits/stdc++.h>
#define ls (id*2)
#define rs (id*2+1)
using namespace std;
typedef long long ll;
const ll N=5e5+5,inf=LLONG_MAX>>2;
ll n,f[N],p;
vector<int>vec[N];
struct node{ll h,v;}a[N];
bool cmph(node x,node y){return x.h!=y.h?x.h>y.h:x.v<y.v;}
bool cmpv(node x,node y){return x.v!=y.v?x.v<y.v:x.h>y.h;}
struct tree{
  ll mi[4*N];
  void change(int id,int l,int r,int x,ll k){
    if(l==r){mi[id]=k;return;}
    int mid=(l+r)>>1;
    if(x<=mid)change(ls,l,mid,x,k);
    else change(rs,mid+1,r,x,k);
    mi[id]=min(mi[ls],mi[rs]);
  }
  ll query(int id,int l,int r,int L,int R){
    if(l==L&&r==R)return mi[id];
    int mid=(l+r)>>1;
    if(R<=mid)return query(ls,l,mid,L,R);
    else if(L>mid)return query(rs,mid+1,r,L,R);
    else return min(query(ls,l,mid,L,mid),query(rs,mid+1,r,mid+1,R));
  }
}t,t2;
inline void get(int id){
  int l=1,r=id,ans;
  while(l<=r){
    int mid=(l+r)>>1;
    if(a[mid].h<=a[id].h+(f[id]>>1))ans=mid,r=mid-1;
    else l=mid+1;
  }
  t.change(1,1,p,a[id].v,f[id]);
  vec[ans-1].push_back(id);
}
int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n;p=n;
  for(int i=1;i<=n;++i)cin>>a[i].h>>a[i].v;
  sort(a+1,a+n+1,cmpv);
  for(int i=1;i<=n;++i)a[i].v=i;
  sort(a+1,a+n+1,cmph);a[n+1].v=++p;
  for(int i=1;i<=4*p;++i)t.mi[i]=t2.mi[i]=inf;
  get(n+1);
  for(int i=n;i>=1;--i){
    for(int j=0;j<vec[i].size();++j){
      int id=vec[i][j];
      t.change(1,1,p,a[id].v,inf);
      t2.change(1,1,p,a[id].v,-a[id].h+((f[id]+1)>>1));
    }
    f[i]=inf;
    f[i]=min(f[i],min(t.query(1,1,p,a[i].v+1,p),t2.query(1,1,p,a[i].v+1,p)+a[i].h));
    get(i);
  }
  cout<<f[1]<<endl;
  return 0;
}