I - Lunar New Year and Red Envelopes

题意：
在长度为n的时间轴上，有k个红包，每个红包有领取时间段[s,t]，价值w，以及领了个这个红包之后，在时间d到来之前无法再进行领取操作。每次领取的策略是取当前可领取红包中w最大的，w相同时取d最大的。再给m个干扰机会，一个干扰机会可以使其在任意一个x这个时间点无法进行领取操作直到x+1。问最优使用不超过m次干扰下，将领取的最小红包价值总和。
题解：
dp[i][j]代表在i时间点前使用了j次disturb所能获得的最少的金额。
1.对于时间点T没有红包可以拿，这个金额就顺延到下一个时刻T+1
          dp[i+1][j] = dp[i][j]
2.如果有红包可以拿，有两种转移方式：
a.不disturb：那么就拿了红包，转移到d+1时间点。
          dp[min(tmp.d + 1, n + 1ll)][l] = min(dp[min(tmp.d + 1, n + 1ll)][l], dp[i][l] + tmp.w);
b.如果还有disturb的机会：就可以不拿红包，转移到T+1时间点。
         dp[i + 1][l] = min(dp[i + 1][l], dp[i][l - 1]);

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxt = 1e5 + 500;
const int maxm = 250;
int n, m, k;
ll dp[maxt][maxm];
void init() {
    for (int i = 2; i < maxt; i++)
        for (int j = 0; j < maxm; j++)
            dp[i][j] = 1e18;
}
struct Ev {
    ll s, t, d, w;
    bool operator<(const Ev& a)const {
        if (w == a.w)
            return d < a.d;
        return w < a.w;
    }
}e[100005];
bool cmp(Ev a, Ev b) {
    if (a.s == b.s) {
        if (a.w == b.w) {
            return a.d > b.d;
        }
        return a.w > b.w;
    }
    return a.s < b.s;
}
priority_queue<Ev> q;
int main() {
    init();
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        cin >> e[i].s >> e[i].t >> e[i].d >> e[i].w;
    }
    sort(e + 1, e + 1 + k, cmp);
    int j = 1;
    for (int i = 1; i <= n; i++) {
        for (; j <= k;) {
            if (e[j].s <= i) {
                q.push(e[j]);
                j++;
            }
            else break;
        }
        while (!q.empty() && q.top().t < i) 
            q.pop();
        if (q.empty()) {
            for (int l = 0; l <= m; l++) {
                dp[i + 1][l] = min(dp[i + 1][l], dp[i][l]);
            }
            continue;
        }
        Ev tmp = q.top();
        for (int l = 0; l <= m; l++) {
            dp[min(tmp.d + 1, n + 1ll)][l] = min(dp[min(tmp.d + 1, n + 1ll)][l], dp[i][l] + tmp.w);
        }
        for (int l = 1; l <= m; l++) {
            dp[i + 1][l] = min(dp[i + 1][l], dp[i][l - 1]);
        }
    }
    ll ans = 1e18;
    for (int i = 0; i <= m; i++) {
        ans = min(ans, dp[n + 1][i]);
    }
    cout << ans << endl;
}