题解 P3084 【[USACO13OPEN]照片Photo】

x义x · 2019-07-29 14:39:45 · 题解

UPD9/27：修正了第二张图片。对大家造成的不便请谅解。

显然这是一个DP题……（当然它也不太显然地是一个差分约束但是被卡了）（其实差分约束还是能过的）

首先定义状态：f[i]表示i位置必须有一头斑点奶牛，（包括i位置的那头牛）前面最多能放多少斑点奶牛。

显然

也就是[j+1,i-1]里不放奶牛，只在f[i]多放一头奶牛。

问题主要在于所谓的满足限制。题意中说一个区间里必须有1头牛，我们把它转化成一个区间里最多有1头牛，最少有1头牛，这是一个常用的技巧。下面分别进行分析。

限制1：区间[l,r]最多有1头奶牛

考虑j<i的两个都在[l,r]中的位置j,i。显然i不能通过j转移得到，不然[l,r]中就会有两头奶牛了。

也就是说：

对于任意包含i的区间[l,r]，合法的j必须小于l。

我们其实不用考虑所有的包含i的区间，我们只需要这些区间里l最小的那一个即可。它的“影响力”最大。

我们定义：minl[i]为包含i的区间中最小的l。我们可以很快地从N到1扫一遍得到它：

可以理解为：包含i的区间要么右端点就是i，要么右端点比i大。

“\text{右端点恰好是}i\text{的区间的最小的}l”很好得出，弄个桶即可。

限制2：区间[l,r]至少有1头奶牛

考虑j<l,r<i的区间[l,r]和位置j,i。显然i不能通过j转移得到，不然[l,r]中一头奶牛也没有。

也就是说：

对于任何r<i（整个区间都在i之前）的区间，合法的j必须大于等于l。

同样，我们其实不用考虑所有的r<i的区间，我们只需要这些区间里l最大的那一个即可。小于它的j都不合法。

（复读ing）

同样我们还是只考虑右端点小于i的最大的l。称它为maxl[i]。我们同样可以从1到N扫一遍得出它：

那么，我们终于得到一个舒服一点的转移方程：

注意到maxl[i],minl[i]都单调不降，所以我们可以使用单调队列优化。参见P1886。

代码如下：

（不建议抄，因为此题细节多的一匹）

#include <bits/stdc++.h>
using namespace std;

int N,M;
int minl[200005],maxl[200005];

int q[200005],h,t;
int f[200005];

int main(){
    //注意我们设了一个虚拟节点N+1判无解 
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N+1;i++) minl[i]=i;
    for(int i=1;i<=M;i++){
        int l,r;scanf("%d%d",&l,&r);
        //这里偷懒了，对应的桶和minl,maxl合并了 
        minl[r]=min(minl[r],l);
        maxl[r+1]=max(maxl[r+1],l);
    }
    //扫 
    for(int i=N;i>=1;i--)
        minl[i]=min(minl[i],minl[i+1]);
    for(int i=1;i<=N+1;i++)
        maxl[i]=max(maxl[i],maxl[i-1]);

    //单调队列和转移部分 
    h=1;q[++t]=0;int j=1;
    for(int i=1;i<=N+1;i++){
        for(;j<minl[i];j++)if(f[j]!=-1){    //新的合法j 
            while(h<=t&&f[q[t]]<f[j]) t--;
            q[++t]=j;
        }
        while(h<=t&&q[h]<maxl[i]) h++;
        if(h<=t) f[i]=f[q[h]]+(i!=N+1);     //选假的N+1不能有贡献 
        else f[i]=-1;
    } 
    printf("%d\n",f[N+1]);

    return 0;
}