[CCO2021] Bread First Search

Rainbow_qwq · 2022-01-21 23:48:33 · 题解

bfs 序会把图分成若干层，考虑 DP 不停的加一层，有一个限制：原有的边不能有从第 i-2 层到第 i 层的；代价则是第 i 层中没有向第 i-1 层有边的。

可以设 f(i,j) 表示分 [i,j] 为一层，转移枚举 f(k,i-1)\to f(i,j)，可以得到 O(n^3) 做法。

但是最终二维的做法还是不太行，需要再挖掘一下转移的性质。

设 f(i) 表示前 i 个分成若干段的代价最小值，考虑从 i\to j(i<j)，发现如下的 j 是不能转移的：

于是我们发现能转移的 j 是一段后缀。设 mx_i 为 (1\sim i)\to v 中 v 的最大值，j 需要 \ge mx_i。并且在 \ge mx_i 的部分，j 每增大 1 代价就增大 1，代价是一段连续的数。

于是推一下就可以简单 O(n) DP 了，可以只向 j 能到的最小地方转移，后面 f(i)+1\to f(i+1)。

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
//#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

bool vis[maxn];
int n,m,f[maxn],sum,mn[maxn],mx[maxn],g[maxn];
vi e[maxn];
void addin(int x){sum+=(!vis[x]),vis[x]=1;}

signed main()
{
    n=read(),m=read();
    For(i,1,n)mn[i]=n+1;
    For(i,1,m){
        int u=read(),v=read();
        mn[u]=min(mn[u],v);
        mn[v]=min(mn[v],u);
        mx[u]=max(mx[u],v);
        mx[v]=max(mx[v],u);
        e[min(u,v)].pb(max(u,v));
    }
    For(i,1,n)mx[i]=max(mx[i],mx[i-1]);
    memset(f,63,sizeof f);
//  For(j,2,n){
//      int sum=0,p=j-1;
//      For(i,max(j,mx[j-1]),n){
//          while(p<i) ++p,sum+=(mn[p]>j-1);
//          f[i]=min(f[i],f[j-1]+sum);
//      }
//  }
    For(j,1,n-1){
        f[j]=min(f[j],f[j-1]+1);
        int nowf=(j==1?0:f[j]);
        addin(j);
        for(auto v:e[j])addin(v);
        // mx[j]
        int to=max(mx[j],j+1);
        f[to]=min(f[to],nowf+to-sum);
    }
    cout<<f[n];
    return 0;
}