【My Problem】流星

Author Avatar
洛水·锦依卫 1月 26, 2019

题面

Background

新年之际,热闹欢腾,大家点竹烟,换红衣,提灯影。

就在这时,有许多流星划过天际。天依惊奇地喊:“哇,是流星诶!”于是大家拿出了大摄影机,决定拍下流星。

Description

因为天依的摄相机框能拍摄到的位置是有限的,而每个流星的轨迹都是一条直线,所以对于每个流星,它们只会在某些时刻在摄相机视野内。已知有 $n$ 只流星,我们能够知道它们的进入与离开摄相机镜头的时间 $Start,End$ 。

天依的相机因为聚焦问题,只能拍摄清楚 $m$ 只流星。当某一秒任意一颗拍摄清楚的流星在摄相框内,那么这一秒就是有流星的,保证流星进入摄相框与离开摄相框的时间为整数。由于大家希望拍摄的视频中相机中有流星的时间尽可能多,所以希望你能够选取最佳的 $m$ 只流星,使得视频中有流星的时间最长。

输入格式

第一行给出 $n,m$,代表流星的数目,以及能够聚焦多少只流星。

之后 $n$ 行,每行 $2$ 个整数 $Start_i,End_i$ 。

输出格式

一个数,表示相机能拍摄到流星的最长时间。

输入输出样例

输入样例1

10 2
4 10
1 5
20 29
6 15
7 18
3 9
15 27
2 8
12 25
13 24

输出样例1

21

样例解释:选取第 $4$、$7$ 只流星即可,它们会在 $6-27$ 的时刻之内出现,共计 $21$ 秒。

输入样例2

10 3
1585793 2073360
1111714 1118555
1043117 1111165
2277346 2455125
438090 829202
3177273 3225550
3600057 4355231
2312872 2605343
427038 433137
1242660 1252942

输出样例2

1633853

数据范围

对于 $10\%$ 的数据,$n<=10$ 。

对于 $50\%$ 的数据,$n<=300$ 。

对于 $100\%$ 的数据,$m<=n<=5000~~~Start_i,End_i<=10^9~。$

题解

考点

$DP​$ ,单调队列优化,排序算吗

10pts

$2^n​$ 暴力枚举嘛……

50pts

很容易想到 $dp$ 是吧?

首先我们把所有线段按左端点排序,这里我们可以很显然地发现,假设线段 $i$ 被线段 $j$ 所包含,也即 $l_i>l_j~~r_i<r_j$ 的话,那么选 $i$ 永远不会比选 $j$ 更优,所以我们把 $i$ 踢出考虑范围,那么剩下的线段必定满足:左端点单调递增,右端点单调递增,也即是这样的:

其中灰线段代表无需考虑的线段。

那么我们可以轻松得到一个 $dp$ 数组:$dp[i][j]$ 代表选到并且已选到第 $i$ 个线段,这是选了的第 $j$ 个线段。设 $len[i]$ 为第 $i$ 个线段的长度,$solve(a,b)$ 为线段 $a$ 与线段 $b$ 的重合长度,那么易得如下转移式:

为什么 $solve$ 函数只用计算 $i$ 和 $k$ 两条线段呢?因为我们按左端点排序了呀 = = ,那么 $i$ 的左端点就必定大于 $k$ 的左端点,别的线段的左右端点又比 $k$ 小,那么不会有线段与 $i$ 的重合部分比 $k$ 的重合部分更多了。

这样就是 $n^3$ 的暴力 $50$ 了。

100pts

还是 $dp$ ,但是我们使用单调队列来优化 O_O 。对于这个单调队列,我们将优化掉 $k$ 的循环部分。

那么怎么做呢?我们的单调队列储存的值,并不是普通的 $dp$ 值保证单调,而是优劣性的单调,保证最前面的队首的一定是最优的转移。

这个单调队列的话说明起来挺麻烦的…… 我们可以想一下贪心选的情况,有线段 $i$ 与线段 $j$ ,$i<j$ ,那么 $l_i<l_j\&\&r_i<r_j$ ,并且 $dp_i < dp_j$ 的情况下,我们在何种可能下选 $j$ 会不如选 $i$ 更优呢?从这里入手即可,先来一张图:

由于我们的右端点单调递增,对于某个线段前面的所有线段肯定都是与第 $k$ 个线段没有交点的,对于这些线段,因为没有重合部分,我们取最大值即可。接着来考虑剩下的线段,它们肯定与 $k$ 有重合部分,那么如何保持单调性呢?我们看图中的线段 $i$ 与 $j$ ,在什么情况下 $i$ 不如 $j$ 更优呢?假设这是选择的第 $x$ 条线段,我们来看 $i$ 与 $j$ 分别对应的转移式:

当选 $j$ 更优时必有: $dp[i][x-1]+len[k]-solve(i,k)<dp[j][x-1]+len[k]-solve(j,k)$

我们将 $solve$ 函数展开即可得:

消项可得:

最后得到

那么可得单调队列弹出条件为队尾与队首的 $dp$ 值之差要大于右端点之差, $k$ 每次转移的时候取队首与前缀最大值转移即可。

同时注意每次转移之前先弹出队首的不相交的线段 = = 。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,f[5001][2],ans,q[5001],head,tail,maxx,len[5001];
struct node
{
    int l,r;
}k[5001];
void Max(int &a,int b){a=a<b?b:a;}
bool cmp(node a,node b){return a.l<b.l;}
int work(int a,int b){return k[a].r-k[b].l<0?0:k[a].r-k[b].l;}
bool pd(int a,int b,int j)
{
    if(f[b][j&1]-f[a][j&1]>k[b].r-k[a].r)
        return true;
    return false;
}
int max(int a,int b){return a<b?b:a;}
int main()
{
    cin>>n>>m;
    for(register int i=1;i<=n;i++)
        scanf("%d%d",&k[i].l,&k[i].r);
    sort(k+1,k+n+1,cmp);
    for(register int i=1;i<=n;i++)len[i]=k[i].r-k[i].l,f[i][1]=len[i],ans=max(len[i],ans);
    for(register int j=2;j<=m;j++)
    {
        q[1]=0;
        head=1,tail=0,maxx=0;
        for(register int i=1;i<=n;i++)
        {
            while(head<=tail&&k[q[head]].r<=k[i].l)
            {
                maxx=max(maxx,f[q[head]][(j-1)&1]);
                head++;
            }
            f[i][j&1]=max(f[q[head]][(j-1)&1]+len[i]-work(q[head],i),maxx+len[i]);
            while(head<=tail&&pd(q[head],i,j-1))
                head++;
            q[++tail]=i;
            ans=max(ans,f[i][j&1]);
        }
    }
    cout<<ans;
}