G

简要题意

给定\(n\)个区间\((l_i,r_i)\)，将这\(n\)个区间分成\(k\)组。要求每组中的区间必须有交，对于每一种划分方案，求每组区间交的长度的和，求所有方案中这个和最大是多少。

数据范围

\(1\leq n,k\leq5000\),\(0\leq l_i,r_i\leq 10^5\)

简要题解

对于处理若干区间的题，通常需要进行预处理，去掉完全包含或被包含的区间。
如果存在区间\(A\)，能够完全包含区间\(B\)，那么\(A\)的分组情况有两种：要么自己单独成为一组，贡献为该区间的长度，要么和它的任一子区间成为一组，贡献为0。
否则，假设区间A和区间C一组，且A与C没有包含关系，那么将A与B分到一组会更优。
接下来我们将区间分成两类\({S_i}\)和\({T_i}\)，\({S_i}\)是能够完全包含某一区间的区间，那么\({T_i}\)中的区间就没有包含关系了。
我们对\({S_i}\)按长度降序排序，\({T_i}\)按右端点坐标升序排序，可以证明，最优的划分方案，一定是将\({T_i}\)分成若干组，且组内下标连续，再把\(S_i\)中最长的若干个区间单独成组。
根据这个思路不难想到动态规划，设\(F[i][j]\)表示，将\({T}\)中前\(i\)个区间分成\(j\)组，能够达到的最大贡献，若不合法则设为\(-inf\)。
状态转移方程：$$F[i][j]=max(F[k-1][j-1]+r_k-l_i+1)$$
需要保证\(k\leq i\)且\(r_k\geq l_i\)。
这里表示将\(T_k\)~\(T_i\)分成一组的情况，枚举\(i,j,k\)，时间复杂度为\(O(n^3)\)。
改写一下转移方程，进行分离变量：$$F[i][j]+l_i-1=max(F[k-1][j-1]+r_k)$$
方程右边是一个只和\(k\)有关的值，可以进行单调队列优化\(Dp\)。
即对于每一个\(j\)，维护一个单调队列\(Q[j]\)，队列中每个元素储存\(F[k-1][j-1]\)和\(r_k\),保证\(r_k\)单增，\(F[k-1][j-1]+r_k\)单减。
每次转移前弹队首，将\(Q_{j-1}\)中\(r_k<l_i\)的扔掉，再直接利用第一个元素转移，并将转移后的信息放入\(Q_j\)队尾。
这样我们得到了\(F[i][j]\)的值，然后枚举一下\({S_i}\)中有几个单独成组，和\(F[i][j]\)合并计算答案即可。
时间复杂度可以优化至\(O(n^2)\)
代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5010;
const ll Inf=1e18;
struct SEC{   int Le,Ri;   }Sec[MAXN];
struct ELE{   int Ri;   ll Num;   };
bool Big[MAXN];
int n,K,Bs;
ll Ans,Blen[MAXN],F[MAXN][MAXN];
deque<ELE>Team[MAXN];
bool cmp2(ll A,ll B){   return A>B;   }
bool cmp(SEC A,SEC B){   return A.Ri==B.Ri?A.Le>B.Le:A.Ri<B.Ri;   }
ll Max(ll A,ll B){   return A>B?A:B;   }
void Prepare()
{   int Maxl=-1;
    sort(Sec+1,Sec+n+1,cmp);
    for(int i=1;i<=n;i++)
    {   Big[i]=Sec[i].Le<=Maxl,Maxl=Max(Maxl,Sec[i].Le);
        if(Big[i]) Blen[++Bs]=Sec[i].Ri-Sec[i].Le+1;
    }
    for(int i=1;i<=n;i++)
        while(Big[i]&&i<=n) swap(Sec[i],Sec[n]),swap(Big[i],Big[n]),n--;
    sort(Sec+1,Sec+n+1,cmp),sort(Blen+1,Blen+Bs+1,cmp2);
    for(int i=1;i<=Bs;i++) Blen[i]+=Blen[i-1];
}
void Solve()
{   for(int i=0;i<=n;i++)
        for(int j=0;j<=K;j++) F[i][j]=-Inf;
    F[0][0]=0;
    for(int i=0;i<=K;i++) Team[i].push_back((ELE){Sec[1].Ri,F[0][i]+Sec[1].Ri});
    for(int i=1;i<=n;i++)
        for(int j=K;j>=1;j--)
        {   while(!Team[j-1].empty()&&Team[j-1][0].Ri<Sec[i].Le) Team[j-1].pop_front();
            if(Team[j-1].empty()) continue ;
            F[i][j]=Team[j-1].front().Num-Sec[i].Le+1;
            ll Num=F[i][j]+Sec[i+1].Ri;
            while(!Team[j].empty()&&Team[j].back().Num<=Num) Team[j].pop_back();
            Team[j].push_back((ELE){Sec[i+1].Ri,Num});
        }
    for(int i=0;i<=K;i++) Ans=Max(Ans,F[n][i]+Blen[K-i]);
}
int main()
{   scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++) scanf("%d%d",&Sec[i].Le,&Sec[i].Ri),Sec[i].Ri--;
    Prepare(),Solve(),printf("%lld\n",Ans);
}