简要题意
给定 \(n\) 个左闭右开的区间 \(A_i = [L_i, R_i)\)，其中 \(0\le L_i < R_i \le x\)，你可以自由选择 \(k\) 个长度为 \(m\) 左闭右开的区间 \(B_j = [l_j, r_j)\) 使得 \(0\le l_j<r_j\le x\)。区间长度定义为内部整点个数。接下来给每个 \(A\) 中的区间 \(A_i\) 分配唯一的一个 \(B\) 中的区间 \(B_{p_i}\)（\(B\) 中区间可以重复使用），你需要最大化 \(\sum_i \operatorname{len}\left([1, x)\backslash(A_i\cup B_{p_i})\right)\)。
数据范围：\(1\le k\le n\le 2000,1\le m\le x\le 10^9\)。
题解
非常好题。
首先考虑如果已经确定了 \(B\)，那么如何确定 \(p_i\)，也就是如何给 \(A\) 中元素分配 \(B\) 中区间。注意到我们需要最大化的是 \(A_i\cap B_{p_i}\) 的 总长度，而 \(B_i\) 长度都相同。那么显然的，\(A_i\) 和 \(B_{p_i}\) 中点越接近就越好。所以其实分配 \(B_i\) 的过程是很优美的：把 \(A\) 按中点坐标排序，那么一定是将其划分为不超过 \(k\) 个连续段，其中每个段内对应的 \(B\) 区间相同。
这样我们很容易设计出一个 2D/1D DP。设 \(f_{i,j}\) 表示前 \(i\) 个区间划分成 \(j\) 段最大的区间交的长度和。记 \(g_{l, r}\) 表示 \(A_{l\dots r}\) 的所有区间如果分为一组，选取的 \(B\) 区间最优时，区间交的长度和。那么转移形如 \(f_{i, j} = \max\limits_{k=1}^{i}f_{k-1, j-1}+g_{k,i}\)。
那么接下来就有两个问题：1. 怎么求出 \(g\)；2. 怎么快速转移 \(f\)。
解决第一个问题需要比较好的直觉。首先，可能的区间有 \(\Theta(x)\) 种，这是不可接受的。第一反应是有没有什么公式或者高妙手段能直接计算出区间位置，但是找了一段时间并没有。那么考虑可行的区间。假设一个候选区间的左端点不是任何一个段内 \(A\) 区间的左端点，右端点也不是任何一个段内区间的右端点，那么把它向左或向右移动一定至少有一个不劣。所以可能的最优区间只有 \(\Theta(n)\) 种。这时候如果预处理出一些前缀和，可以 \(\Theta(n^3)\) 算出所有 \(g\) 的值。这显然不够。对 \(g\) 的一些洞察告诉我们，记 \(g_{l,r}\) 的决策点为 \(t_{l,r}\)，则 \(t_{l-1,r}\le t_{l,r}\le t_{l,r+1}\)。直接运用决策单调性优化做到 \(\Theta(n^2)\)。
第二个问题比较好解决。首先注意到记录 \(j\) 是为了限制区间不超过 \(k\) 个，于是直接上一个 wqs 二分（aliens trick）即可做到平方 \(\log\)。另一种方法则是注意到 \(g\) 满足四边形不等式（这其实是根据 DP 方程的形状猜到的），那么 \(f\) 具有决策单调性，于是就做到了 \(\Theta(n^2)\)。
我用了 wqs 二分。
代码
// Author: kyEEcccccc
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)
const int N = 2005;
int n, k, x, m, nn;
struct Seg { int l, r; } a[N];
vector<int> p;
int opt[N][N];
LL f[N], g[N][N], w[N << 1][N];
int h[N];
LL intersect(Seg a, Seg b)
{
if (a.l > b.l) swap(a, b);
if (a.r <= b.l) return 0;
return min(a.r, b.r) - b.l;
}
void compute_g(void)
{
F(i, 1, nn) F(j, 1, n)
w[i][j] = w[i][j - 1] + intersect({p[i], p[i] + m}, a[j]);
FF(d, n - 1, 0) F(l, 1, n - d)
{
int r = l + d;
int pl = l == 1 ? 1 : opt[l - 1][r],
pr = r == n ? nn : opt[l][r + 1];
// cerr << l << ' ' << r << ' ' << pl << ' ' << pr << '\n';
// pl = 1, pr = nn;
g[l][r] = LLONG_MIN / 2;
F(i, pl, pr)
{
if (g[l][r] < w[i][r] - w[i][l - 1])
{
opt[l][r] = i;
g[l][r] = w[i][r] - w[i][l - 1];
}
}
}
}
pair<int, LL> compute(LL slp)
{
F(i, 1, n)
{
pair<LL, int> fr = {g[1][i], 0};
F(j, 1, i - 1) MAX(fr, make_pair(f[j] + g[j + 1][i], -h[j]));
f[i] = fr.first - slp; h[i] = -fr.second + 1;
}
return {h[n], f[n]};
}
signed main(void)
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(nullptr);
cin >> n >> k >> x >> m;
LL ans = (LL)x * n - (LL)m * n;
F(i, 1, n)
{
cin >> a[i].l >> a[i].r;
ans -= a[i].r - a[i].l;
p.push_back(a[i].l + m > x ? x - m : a[i].l);
p.push_back(a[i].r - m < 0 ? 0 : a[i].r - m);
}
sort(a + 1, a + n + 1, [] (Seg a, Seg b)
{ return a.l + a.r < b.l + b.r; });
sort(p.begin(), p.end());
p.resize(unique(p.begin(), p.end()) - p.begin());
nn = p.size();
p.insert(p.begin(), 0);
compute_g();
LL cl = 0, cr = 2000000000000LL, ca, cc;
while (cl <= cr)
{
LL cm = (cl + cr) >> 1;
pair<int, LL> res = compute(cm);
if (res.first <= k)
ca = res.second, cc = cm, cr = cm - 1;
else cl = cm + 1;
}
cout << ca + ans + cc * k << '\n';
return 0;
}