洛谷P3084 [USACO13OPEN]Photo G

@Pelom  October 12, 2021

题意

有$n$头奶牛,$m$条约束$(a_i,b_i)$,表示$a_i$到$b_i$间有且仅有一头带斑点的奶牛,求最多可能有多少只斑点奶牛

数据范围:$1 \le n \le 200000,1 \le m \le 100000$

题解

有且仅有一头拆解为至多一头+至少一头
初步思路为差分约束,但明显复杂度过高
发现可以$dp$,用$f[i]$表示第$i$头奶牛有斑点的情况下前$i$头奶牛最多有多少斑点,易得状态转移方程$$f[i]=max(f[j]+1)$$其中$j < i$且满足上述约束
现在思考如何找到所有满足约束的$j$
由每个区间最多有一个斑点,不能放在包含$i$的区间里,需要记录所有包含$i$的区间的$l$的最小值$r[i]$,$j \le r[i]$
由每个区间最少有一个斑点,小于$i$且不包含$i$的区间中要放一个,需要记录所有不包含$i$的区间的$l$的最大值$l[i]$,$j \ge l[i]$
$dp$时$j$的取值范围为$[l[i],r[i]]$
读入$(a_i,b_i)$时,用$a_i-1$更新$r[b_i]$,用$a_i$更新$l[b_i+1]$

for(int i=1;i<=m;i++){
    scanf("%d%d",&a,&b);
    r[b]=min(r[b],a-1);
    l[b+1]=max(l[b+1],a);
}

发现状态转移方程只与$j$有关,可以使用单调队列优化

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200000+10;
int n,m,a,b;
int h,t;
int l[N],r[N],q[N],dp[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+1;i++)
        r[i]=i-1;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        r[b]=min(r[b],a-1);
        l[b+1]=max(l[b+1],a);
    }
    for(int i=n;i;i--)
        r[i]=min(r[i],r[i+1]);
    for(int i=2;i<=n+1;i++)
        l[i]=max(l[i],l[i-1]);
    q[h=t=1]=0;
    for(int i=1,j=1;i<=n+1;i++){
        for(;j<=r[i] && j<=n;j++){
            if(dp[j]==-1)
                continue;
            for(;h<=t && dp[j]>dp[q[t]];t--);
            q[++t]=j;
        }
        for(;h<=t && q[h]<l[i];h++);
        if(h<=t)
            dp[i]=dp[q[h]]+(i<n+1);
        else dp[i]=-1;
    }
    printf("%d",dp[n+1]);
    return 0;
}

添加新评论