洛谷3084 [USACO13OPEN]Photo

题解 动态规划 动态规划-单调队列优化DP 省选/NOI-
题目链接 编辑文章

题意

有 $n(n\le 2\times 10^5)$ 头奶牛,有 $m(m\le 10^5)$ 组关系 $(l,r)$ ,表示 $[l,r]$ 奶牛中有且仅有一头有斑点。问最多有多少头奶牛有斑点。

题解

第一反应就是差分约束,不过因为是从DP点进来的所以我去看题解确认了下,得知会T(除了玄学的限定次数)。

方程式还好想,就是转移比较神奇。用 $f[i]$ 表示第 $i$ 头牛有斑点的前提下前 $i$ 头牛最多有多少有斑点。对于一些满足条件的点 $j$ ,可以得到方程:

$$f[i]=f[j]+1$$

$j$ 需要满足以下限定条件:

  1. $j < i$ 废话
  2. $j$ 在所有包含 $i$ 的区间的前面(最多一个)
  3. 对于所有整个都在 $i$ 前面的区间,$j$ 必须在区间中(至少一个)

可以通过上面的条件预处理出满足条件的 $j$ 的区间 $[L_i,R_i]$ ,然后单调队列优化DP。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=200005;
int n,m,a,b,L[N],R[N],q[N],f[N];

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n+1;i++) R[i]=i-1;
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        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]);
    int l=1,r=1,j=1; q[1]=0;
    for (int i=1;i<=n+1;i++)
    {
        int maxj=min(R[i],n);
        for (;j<=maxj;j++)
        {
            if (f[j]==-1) continue;
            while (l<=r && f[q[r]]<=f[j]) r--;
            q[++r]=j;
        }
        while (l<=r && q[l]<L[i]) l++;
        if (l<=r) f[i]=f[q[l]]+(i<=n);
        else f[i]=-1;
    }
    return !printf("%d",f[n+1]);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空