题解 P3463 [POI2007] EGZ-Driving Exam

Find_Yourself · 2023-10-14 18:42:06 · 题解

树状数组优化 DP。

显然，如果 i 能到 1，那么 j(1\le j<i) 也能到 1；

同理，如果 i 能到 n，那么 j(i<j\le n) 也能到 n。

定义 l_i 表示从 i 到 1 至少要加多少条边，r_i 表示从 i 到 n 至少要加多少条边。

答案为 \left[\max\limits_{i=1}^{n}\max\limits_{j=1}^{n}[r_j\le k-l_i]i-j+1\right]-\sum\limits_{i=1}^{n}[l_i=r_i=0]。用一个指针维护就可以了。

考虑将 l,r 分开求。

我们从上到下，从左到右枚举每一条边，转移方程为 l_i=\min\limits_{j=1}^{i-1}(l_j+i-j-1)。将贡献拆一下，用树状数组维护 (l_i-i) 的前缀最小值，每次算完后更新树状数组即可。r_i 同理。

复杂度 O(n\log n)。注意初始值等细节。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n,len,m,k,ta,tb,c[N],f[N],g[N];
struct node{int x,h;node(int x=0,int h=0):x(x),h(h){}}a[N],b[N];
inline bool cmp(node x,node y){return x.h==y.h?x.x<y.x:x.h>y.h;}
inline bool cmp2(node x,node y){return x.h==y.h?x.x>y.x:x.h>y.h;}
inline int lbt(int x){return x&(-x);}
inline void upd(int i,int v){for(;i<=n;i+=lbt(i))c[i]=min(c[i],v);}
inline int get(int i){int res=1e9;for(;i;i-=lbt(i))res=min(res,c[i]);return res;}
int main(){
  cin>>n>>len>>m>>k;
  for(int i=1;i<=m;++i){
    int x=read(),w=read(),d=read();++w;
    if(!d)a[++ta]=node(x,w);
    else b[++tb]=node(x+1,w);
  }
  sort(a+1,a+ta+1,cmp2);sort(b+1,b+tb+1,cmp);
  memset(c,-1,sizeof(c));
  for(int i=1;i<=n;++i)f[i]=i-1;
  for(int i=1;i<=tb;++i){
    int x=b[i].x;
    f[x]=get(x-1)+x-1;
    upd(x,f[x]-x);
  }
  for(int i=1;i<=n;++i)f[i]=min(f[i],get(i-1)+i);
  memset(c,-1,sizeof(c));
  for(int i=1;i<=n;++i)g[i]=n-i;
  for(int i=1;i<=ta;++i){
    int x=n-a[i].x+1;
    g[a[i].x]=get(x-1)+x-1;
    upd(x,g[a[i].x]-x);
  }
  for(int i=1;i<=n;++i)g[i]=min(g[i],get(n-i)+n-i+1);
  int tmp=0;
  for(int i=1;i<=n;++i){
    if(!f[i]&&!g[i]){
      ++tmp;
    }
  }
  int cur=1,ans=0;
  for(int i=1;i<=n;++i){
    int t=k-f[i];
    while(cur<=n&&g[cur]>t)++cur;
    ans=max(ans,i-cur+1-tmp);
  }
  cout<<ans<<endl;
  return 0;
}