题目链接：
http://www.icpc.moe/onlinejudge/showProblem.do?problemCode=3941
题解：
先吧所给的区间合并，得到若干个独立的区间。
然后从左到右把所有的区间都铺满个，并且对每个独立的区间的最后一个点考虑放和不放两种情况（dfs做，总复杂度也就2^10），然后去所有答案里面最大的那个。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL; int n, k, m; struct Node {
LL l, r;
bool operator < (const Node& tmp) const {
return l < tmp.l || l == tmp.l&&r < tmp.r;
}
}arr[], nds[]; int tot; //pos表示当前已经覆盖到了pos-1的位置，从pos开始是还未覆盖的部分
void solve(LL pos, int cur, LL cnt, LL ret, LL &ans) {
if (cnt > m) return;
if (cur == tot || cnt == m) {
ans = max(ans, ret); return;
}
LL lef, len, sum;
if (pos <= nds[cur].r) {
lef = max(pos, nds[cur].l);
len = nds[cur].r - lef + ;
sum = len / k;
if (len%k) sum++;
if (cnt + sum>m) { ans = max(ans, ret + (m - cnt)*k); }
//最后一个点不放
solve(lef + k*sum, cur + , cnt + sum, ret + sum*k, ans);
//最后一个点放
solve(nds[cur].r + k, cur + , cnt + sum + , ret + nds[cur].r + k - lef, ans);
}
else {
//最后一个点不放
solve(pos, cur + , cnt, ret, ans);
//最后一个点放
solve(max(pos, nds[cur].r + k), cur + , cnt + , ret + max((LL), nds[cur].r + k - pos), ans);
}
} int main() {
int tc;
scanf("%d", &tc);
while (tc--) {
tot = ;
scanf("%d%d%d", &n, &k, &m);
for (int i = ; i < n; i++) {
scanf("%lld%lld", &arr[i].l, &arr[i].r);
}
sort(arr, arr + n);
//合并区间
for (int i = ; i < n; i++) {
if (tot == ) {
nds[tot++] = arr[i];
}
else {
if (arr[i].l <= nds[tot - ].r) {
nds[tot - ].r = max(nds[tot - ].r, arr[i].r);
}
else {
nds[tot++] = arr[i];
}
}
}
LL ans = ;
solve(, , , , ans);
printf("%lld\n", ans);
}
return ;
}