P14198

设

A,B

为

a,b

的前缀和，

w(l,r)

是区间

[l,r]

的权值。显然，这个权值函数几乎是上凸的，想到决策单调性优化 DP。但是这不一定对，有可能

w(a,c)+w(b,d)

刚好卡在升级之前，导致比

w(a,d)+w(b,c)

小

1

。

一个巧妙的想法是，把

w

补全成连续的函数，使其具有决策单调性。设

w'(x)

，假设

w(x)=k

，则让

k

级和

k+1

级中间的升级变成一次函数，即

w'(x)=k+\frac{x-B_k}{b_{k+1}}

。

w'

是连续且上凸的。这时我们有 DP

f_i=\lfloor\max_{j=0}^{i-1}\{f_j+w'(j+1,i)\}\rfloor

。这也有决策单调性，因为在四边形不等式中

f

是抵消的。

w'

单次算

O(\log m)

，此时二分队列或用 1log 的决策单调性分治可做到

O(m+n\log n\log m)

。

CPP

#include<bits/stdc++.h>
using namespace std;
int t,n,m,c,p[500005];
long long a[500005],b[500005];
double f[500005];
double calc(int l,int r){
  int k=upper_bound(b+1,b+m+1,a[r]-a[l])-b-1;
  return k+1.0*(a[r]-a[l]-b[k])/(b[k+1]-b[k])-c;
}
void solve(int l,int r){
  if(l==r){
    f[l]=floor(f[l]);
    return;
  }
  int mid=(l+r)>>1;
  for(int i=p[l-1];i<=p[r];i++)if(f[i]+calc(i,mid)>f[mid])f[mid]=f[i]+calc(i,mid),p[mid]=i;
  solve(l,mid);
  for(int i=l;i<=mid;i++)if(f[i]+calc(i,r)>f[r])f[r]=f[i]+calc(i,r),p[r]=i;
  solve(mid+1,r);
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cin>>t;
  while(t--){
    cin>>n>>m>>c,b[m+1]=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
    for(int i=1;i<=m;i++)cin>>b[i],b[i]+=b[i-1];
    for(int i=1;i<=n;i++)f[i]=calc(0,i),p[i]=0;
    solve(1,n),cout<<(long long)f[n]<<'\n';
  }
  return 0;
}

考虑优化，使用二分队列，瓶颈是最后一步，要求两个决策点

j<i

的分界点。考虑实际上我们关心的是序列上的位置的

w

，从

w'

的分界点开始中间有一段区间按

w

转移相同，我们可以任意分给

i

或

j

。我们可以求

w

的分界点，也就是使

i

恰好升级的位置，二分出升了

k

级使

a_j+B_{k+f_i-f_j}>a_i+B_k

。然后就可以再二分使从

i

开始升了

k

级的位置。

具体来说，

w'

的分界点是最小的

x

使

f_i+w'(x)>f_j+w'(x+B_i-B_j)

，

w

的分界点则是第一个满足

f_i+w(x)>f_j+w(x+B_i-B_j)

的

x

，最晚的分界点不能在

f_i+w(x)>f_j+w(x+B_i-B_j)

且存在

x=B_k-B_i

的第一个位置之后。我们取的分界点是

w

的分界点后第一个序列上的位置。

复杂度

O(m+n\log m)

。

CPP

#include<bits/stdc++.h>
using namespace std;
int t,n,m,c;
long long a[500005],b[500005];
double f[500005];
struct node{
  int p,l,r;
}q[500005];
double calc(int l,int r){
  int k=upper_bound(b+1,b+m+1,a[r]-a[l])-b-1;
  return k+1.0*(a[r]-a[l]-b[k])/(b[k+1]-b[k])-c;
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cin>>t;
  while(t--){
    cin>>n>>m>>c,b[m+1]=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
    for(int i=1;i<=m;i++)cin>>b[i],b[i]+=b[i-1];
    int bp=1,fp=1;
    q[1]=(node){0,1,n};
    for(int i=1;i<=n;i++){
      while(q[bp].r<i)bp++;
      f[i]=floor(f[q[bp].p]+calc(q[bp].p,i));
      while(fp>bp&&f[i]+calc(i,q[fp].l)>f[q[fp].p]+calc(q[fp].p,q[fp].l))fp--;
      int p;
      if(f[i]<=f[q[fp].p])p=n+1;
      else if(f[i]>f[q[fp].p]+m)p=i+1;
      else{
        int l=0,r=m-f[i]+f[q[fp].p]+1;
        while(l<r){
          int mid=(l+r)>>1;
          if(a[q[fp].p]+b[(int)(mid+f[i]-f[q[fp].p])]>a[i]+b[mid])r=mid;
          else l=mid+1;
        }
        p=lower_bound(a+1,a+n+1,a[i]+b[l])-a;
      }
      if(p<=n)q[fp].r=p-1,q[++fp]=(node){i,p,n};
    }
    cout<<(long long)f[n]<<'\n';
  }
  return 0;
}

文章操作

相关推荐

评论

P14198