有 n n n场音乐节，每场音乐节都会持续一定的天数，并且在这期间每一天都可以参加一次音乐派对，共可以参加 m m m次。参加完一次音乐派对后，快乐都会持续 k k k天（包括参加派对的那天）。问怎么参加能让快乐的天数最多，并输出快乐的天数。
用递归来贪心。先将区间合并，减轻判断的压力。 主体题解均写入注释。
#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <functional> #include <iostream> #include <map> #include <queue> #include <stack> #include <string> #include <unordered_map> #include <vector> #define lowbit(x) ((x) & -(x)) using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 1e6 + 10, NN = 2e3 + 10, INF = 0x3f3f3f3f, LEN = 20; const ll MOD = 1e9 + 7; const ull seed = 31; inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } struct Day { ll s, e, sum; bool friend operator<(const Day& a, const Day& b) { if (a.s == b.s) return a.e < b.e; return a.s < b.s; } } day[N]; ll n, k, m, ans, top; void dfs(ll id, ll now, ll sum, ll maxx) { if (id > top || sum == 0) { ans = max(maxx, ans); return; } now = max(now, day[id].s); ll num = (day[id].e - now + 1 + (k - 1)) / k; //求出本区间内有多少天可使快乐最大化。加上(k-1)的目的是为了保证这段区间能取就取，还有是为了于now>day[id].e的情况，保证num==0 if (num >= sum) { //sum不够用了，直接结束 ans = max(ans, maxx + sum * k); return; } dfs(id + 1, now + num * k, sum - num, maxx + num * k);//理想状态 dfs(id + 1, day[id].e + k, sum - num - 1, maxx + day[id].e + k - now);//取上最后一个点。上一个dfs也有可能取过最后一个点，但是不影响最终情况，因为这个情况一定不是最优解 } void init() { ans = 0; top = 1; } int main() { int T; T = read(); while (T--) { init(); scanf("%lld%lld%lld", &n, &k, &m); for (int i = 1; i <= n; i++) { scanf("%lld%lld", &day[i].s, &day[i].e); day[i].sum = day[i].e - day[i].s + 1; } sort(day + 1, day + 1 + n); for (int i = 2; i <= n; i++) {//区间合并 if (day[top].e + 1 >= day[i].s) day[top].e = max(day[top].e, day[i].e); else { day[++top].s = day[i].s; day[top].e = day[i].e; } } dfs(1, 0, m, 0); printf("%lld\n", ans); } return 0; }