P3084 [USACO13OPEN]照片Photo

想不到*2QwQ

思路：转化+DP

提交：1次

题解：

这个真想不到去DP。
我们设 (f[i]) 表示让第 (i) 个牛是斑点牛，那么我们需要考虑如何转移是合法的。
(l[i]) 表示在 (i) 左侧所有不包含 (i) 的区间中最靠右的左端点，(r[i]) 表示所有包含 (i) 的区间中最靠左的左端点；
即 (i) 保证可以覆盖 ([r[i],i])，并且不能覆盖到(l[i])，否则以 (l[i]) 为左端点的区间就会因为 (i) 占的区间太远而无法被别的点覆盖到（这个区间不与 (i) 相交）
所以 (f[i]=max_{l[i]<j<r[i]}(f[j]+1))
由于 (l[i],r[i]) 单调不降，所以我们可以单调队列维护。

#include<bits/stdc++.h>
#define R register int
using namespace std;
namespace Luitaryi {
inline int g() { R x=0,f=1;
  register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
  do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;
} const int N=230010;
int n,m;
int l[N],r[N],f[N],q[N];
inline void main() {
  n=g(),m=g(); 
  for(R i=1;i<=n+1;++i) r[i]=i;
  for(R i=1,LL,RR;i<=m;++i) 
    LL=g(),RR=g(),l[RR+1]=max(l[RR+1],LL),r[RR]=min(r[RR],LL);
  for(R i=2;i<=n+1;++i) l[i]=max(l[i-1],l[i]);
  for(R i=n;i;--i) r[i]=min(r[i+1],r[i]);
  R h=1,t=1,p=1; for(R i=1;i<=n+1;++i) {
    while(p<r[i]&&p<=n) {
      if(f[p]!=-1) {
        while(h<=t&&f[q[t]]<f[p]) --t; q[++t]=p; 
      } ++p;
    } while(h<=t&&q[h]<l[i]) ++h;
    if(h<=t) f[i]=f[q[h]]+(i!=n+1);
    else f[i]=-1;
  } printf("%d
",f[n+1]);
}
} signed main() {Luitaryi::main(); return 0;}

2019.09.26
50