JZOJ 6367 工厂

区间题套路：考虑所有区间互不相交的情况，并考虑互相包含的区间之间的关系。
此题类似。

首先考虑所有区间互不相交的情况。
区间按左端点排序（此时右端点一定也有序），这样一组必定是一段区间。
并且只要交集不为空，交集大小即这一组第一个区间右端点减去最后一个区间左端点。

于是得到一个 DP：设 fi,j 表示前 i 个区间分 j 组的最大答案。
转移即枚举该组的区间，得 fi,j=max1≤k≤i,tk>si(fk−1,j+tk−si)

然后考虑互相包含的区间之间的关系。
若区间 a,b 满足 b⊆a，则只有以下两种情况：
1. a,b 与某些区间在同一组。 2. a 单独在一组，b 与某些区间在一组。 证明：若 a 与某些区间在一组，则将 a 移动到 b 所在的组，a 原来的组交集不会变小，b 所在的组答案不变。

于是把不包含别的区间的区间拉出来 DP，枚举这一部分在 p 组中占了多少组，别的组贪心地在另一部分取更大的区间，剩下的分进任意一个所包含的区间所在的组（答案不变）。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 200;
int n,p;
int vis[N + 5];
int tot1,tot2;
int f[N + 5][N + 5],ans = -0x3f3f3f3f;
struct note
{
    int l,r;
    inline bool operator<(const note &o) const
    {
        return l < o.l;
    }
    inline bool operator>(const note &o) const
    {
        return r - l > o.r - o.l;
    }
} w[N + 5],a[N + 5],b[N + 5];
int main()
{
    freopen("factory.in","r",stdin),freopen("factory.out","w",stdout);
    scanf("%d%d",&n,&p);
    for(register int i = 1;i <= n;++i)
        scanf("%d%d",&w[i].l,&w[i].r);
    for(register int i = 1,flag;i <= n;++i)
    {
        flag = 1;
        for(register int j = 1;j <= n;++j)
            if((i ^ j) && !vis[j] && w[i].l <= w[j].l && w[j].r <= w[i].r)
            {
                flag = 0;
                break;
            }
        flag ? (a[++tot1] = w[i]) : (vis[i] = 1,b[++tot2] = w[i]);
    }
    sort(a + 1,a + tot1 + 1),sort(b + 1,b + tot2 + 1,greater<note>()),memset(f,-0x3f,sizeof f),f[0][0] = 0;
    for(register int i = 1;i <= tot1;++i)
        for(register int j = 1;j <= p;++j)
            for(register int k = 1;k <= i;++k)
                if(a[k].r > a[i].l)
                    f[i][j] = max(f[i][j],f[k - 1][j - 1] + a[k].r - a[i].l);
    for(register int i = p,sum = 0;i && p - i <= tot2;sum += b[p - i + 1].r - b[p - i + 1].l,--i)
        i <= tot1 && (ans = max(ans,f[tot1][i] + sum));
    printf("%d\n",ans);
}