P3084 [USACO13OPEN]照片Photo
斯德哥尔摩
2018-10-29 18:34:05
[P3084 [USACO13OPEN]照片Photo](https://www.luogu.org/problemnew/show/P3084)
设$dp[i]$表示到第$i$个位置为止且第$i$个位置必放，最多能放多少个。
有两个限制条件：每个区间至少一个，每个区间至多一个。
因为一个区间至多一个，所以所有包含这个点的区间都不能再放，要找到所有包含这个点的区间中最小的左端点，令$Right[i]=\text{左端点}-1$。
因为一个区间至少一个，所以不能有地方空着不放，找到整个区间在当前点之前的区间，取最大的左端点，令$Left[i]=\text{左端点}$。
每一次读入的时候，用$l$更新$Left[y+1]$，用$l-1$更新$Right[y]$。
然后正着扫一遍，用$Left[i-1]$更新$Left[i]$，因为在$i-1$之前的左端点必定在$i$之前；
同理再倒着扫一遍，用$Right[i+1]$更新$Right[i]$。
然后状态转移：
$$dp[i]=\max\{dp[j]+1\ |\ j\in[Left[i],Right[i]]\}$$
开个单调队列优化一下就好。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<deque>
#define MAXN 200010
using namespace std;
deque<int> q;
int n,m;
int Left[MAXN],Right[MAXN],dp[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
q.push_back(0);
for(int i=1,j=1;i<=n+1;i++){
while(j<=Right[i]&&j<=n){
if(dp[j]==-1){j++;continue;}
while(!q.empty()&&dp[j]>dp[q.back()])q.pop_back();
q.push_back(j);
j++;
}
while(!q.empty()&&q.front()<Left[i])q.pop_front();
if(!q.empty())dp[i]=dp[q.front()]+(i!=n+1?1:0);
else dp[i]=-1;
}
printf("%d\n",dp[n+1]);
}
void init(){
int x,y;
n=read();m=read();
for(int i=1;i<=n+1;i++)Right[i]=i-1;
for(int i=1;i<=m;i++){
x=read();y=read();
Left[y+1]=max(Left[y+1],x);
Right[y]=min(Right[y],x-1);
}
for(int i=n;i>=1;i--)Right[i]=min(Right[i],Right[i+1]);
for(int i=2;i<=n+1;i++)Left[i]=max(Left[i],Left[i-1]);
}
int main(){
init();
work();
return 0;
}
```