ZOJ 3941 Kpop Music Party 贪心

题目链接：

http://www.icpc.moe/onlinejudge/showProblem.do?problemCode=3941

题解：

先吧所给的区间合并，得到若干个独立的区间。

然后从左到右把所有的区间都铺满个，并且对每个独立的区间的最后一个点考虑放和不放两种情况（dfs做，总复杂度也就2^10），然后去所有答案里面最大的那个。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 int n, k, m;
 9 
10 struct Node {
11     LL l, r;
12     bool operator < (const Node& tmp) const {
13         return l < tmp.l || l == tmp.l&&r < tmp.r;
14     }
15 }arr[11], nds[11];
16 
17 int tot;
18 
19 //pos表示当前已经覆盖到了pos-1的位置，从pos开始是还未覆盖的部分
20 void solve(LL pos, int cur, LL cnt, LL ret, LL &ans) {
21     if (cnt > m) return;
22     if (cur == tot || cnt == m) {
23         ans = max(ans, ret); return;
24     }
25     LL lef, len, sum;
26     if (pos <= nds[cur].r) {
27         lef = max(pos, nds[cur].l);
28         len = nds[cur].r - lef + 1;
29         sum = len / k;
30         if (len%k) sum++;
31         if (cnt + sum>m) { ans = max(ans, ret + (m - cnt)*k); }
32         //最后一个点不放
33         solve(lef + k*sum, cur + 1, cnt + sum, ret + sum*k, ans);
34         //最后一个点放
35         solve(nds[cur].r + k, cur + 1, cnt + sum + 1, ret + nds[cur].r + k - lef, ans);
36     }
37     else {
38         //最后一个点不放
39         solve(pos, cur + 1, cnt, ret, ans);
40         //最后一个点放
41         solve(max(pos, nds[cur].r + k), cur + 1, cnt + 1, ret + max((LL)0, nds[cur].r + k - pos), ans);
42     }
43 }
44 
45 int main() {
46     int tc;
47     scanf("%d", &tc);
48     while (tc--) {
49         tot = 0;
50         scanf("%d%d%d", &n, &k, &m);
51         for (int i = 0; i < n; i++) {
52             scanf("%lld%lld", &arr[i].l, &arr[i].r);
53         }
54         sort(arr, arr + n);
55         //合并区间
56         for (int i = 0; i < n; i++) {
57             if (tot == 0) {
58                 nds[tot++] = arr[i];
59             }
60             else {
61                 if (arr[i].l <= nds[tot - 1].r) {
62                     nds[tot - 1].r = max(nds[tot - 1].r, arr[i].r);
63                 }
64                 else {
65                     nds[tot++] = arr[i];
66                 }
67             }
68         }
69         LL ans = 0;
70         solve(0, 0, 0, 0, ans);
71         printf("%lld
", ans);
72     }
73     return 0;
74 }