[ USACO 2013 OPEN ] Photo

\(\\\)

Description

有一个长度为 \(n\) 的奶牛队列，奶牛颜色为黑或白。

现给出 \(m\) 个区间 \([L_i,R_i]\) ，要求：每个区间里 有且只有一只黑牛 。

问满足所有给出限制最少有多少头黑牛，若无合法方案输出 \(-1\) 。

\(n\le 2\times 10^5,m\le 10^5\)

\(\\\)

Solution

单调队列优化。

设 \(f[i]\) 表示，第 \(i\) 个位置为黑牛， \([1,i]\) 的设置符合所有限制，最少有多少头黑牛。

考虑合法的转移区间的限制有哪些。

每个区间里只能有一头黑牛。

这个限制说明，所有包含 \(i\) 的区间里，都不能再有黑牛，所以转移区间右端点为，包含 \(i\) 的区间里最小的的 \(L_i-1\) 。
每个区间里必须有一头黑牛。

这个限制比较麻烦。因为不能有区间空着，所以所有不包含 \(i\) 的区间里都要有黑牛。

所以我们要找到，不包含 \(i\) 的区间里最大的 \(L_i\)，转移的右端点就是这个 \(L_i\) 。

然后就可以单调队列优化了。注意不合法状态不放到单调队列里。

\(\\\)

Code

写起来其实还是可以判断代码能力的。

有一种比较优秀的写法不知道比我原来yy的高到哪里去了，利用了一个单调性。

一个点转移的合法区间左右端点其实都有单调性。

如果包含这个位置的最左端点要小于上一个位置，显然上一个位置可以直接换成这个值。

如果不包含这个位置的最右端点要小于上一个位置，显然这个位置的右端点也可以直接换成上一个位置的值。

这样一来我们的预处理是线性的了，也就是说，对于每个区间，我们只需要标记区间右端点和区间右端点 \(+1\) 的位置，最后扫描一遍所有位置。

还有一个技巧是统计答案的时候，不需要讨论最后一个位置什么颜色，只需要让数列长度 \(+1\) , 最后一个位置的 \(f\) 值就是答案。

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 200010

#define R register

#define gc getchar

#define inf 2000000000

using namespace std;

inline int rd(){

  int x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

int n,m,l[N],r[N],f[N],q[N],hd,tl;

int main(){

  n=rd(); m=rd();

  for(R int i=1;i<=n+1;++i) r[i]=i-1;

  for(R int i=1,sl,sr;i<=m;++i){

    sl=rd(); sr=rd();

    r[sr]=min(r[sr],sl-1);

    l[sr+1]=max(l[sr+1],sl);

  }

  for(R int i=1;i<=n+1;++i) l[i]=max(l[i],l[i-1]);

  for(R int i=n;i;--i) r[i]=min(r[i],r[i+1]);

  int ptr=1; hd=tl=1;

  for(R int i=1;i<=n+1;++i){

    while(ptr<=r[i]){

      if(f[ptr]<0){++ptr;continue;}

      while(f[ptr]>f[q[tl]]&&hd<=tl) --tl;

      q[++tl]=ptr; ++ptr;

    }

    while(q[hd]<l[i]&&hd<=tl) ++hd;

    if(hd<=tl) f[i]=f[q[hd]]+(i!=n+1);

    else f[i]=-1;

  }

  printf("%d\n",f[n+1]);

  return 0;

}

巴特西

[ USACO 2013 OPEN ] Photo

Description

Solution

Code

最新文章

热门文章