斯德哥尔摩 的博客

斯德哥尔摩 的博客

P3084 [USACO13OPEN]照片Photo

posted on 2018-10-29 18:34:05 | under 刷题 |

P3084 [USACO13OPEN]照片Photo

设$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]]\}$$

开个单调队列优化一下就好。

附代码:

#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;
}