Codeforces 1106E (倒序DP + Set)

发表于 | 分类于 | | + s

Codeforces 1106E
题意：有 $k$ 个区间 $[s_j, t_j]$ 表示一段时间，每个区间有 $t_j, w_j$ 表示若选择这个区间则 $t_j$ 后才能选其他的区间，选择区间的权为 $w_j$ 。现在有一个人从 $1$ 时刻开始选区间，他会选当前能选的最大权的区间，若存在多个，选 $d_j$ 大的区间。现在有 $m$ 次机会，每次可以使得这个人在某一秒不能选区间。求当这 $m$ 次机会使用得最优时，这个人最小能选择区间权和。

正序DP不太好做。
考虑倒序DP，设$dp(i,j)$为$[i,n]$用了$j$次机会的最小权和。
则
$$
dp(i,j)=\min(dp(i+1,j-1),dp(i+1,j),dp(g, j))
$$
其中$g=\max\limits_{i \in {[s_j, t_j], j\in[1,k]}}(d_j)$

这个$g$可以用set维护。
具体就是将区间端点存起来，然后枚举时间线时看是否超出了，超出即删掉，如果有新的加入，就加入。

知识点：
1、倒序DP方法可以使正序DP时多个转移变成一个转移

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL n, m, k;
    vector<pair<LL, LL > > st[100000 + 5], ed[100000 + 5];
    LL dp[100000 + 5][200 + 5];
    multiset<pair<LL, LL > > S;

    void clean() {
        ms(dp, 0);
    }
    int solve() {

        clean();
        cin >> n >> m >> k;
        for (LL s, t, d, w, i = 1; i <= k; ++i) {
            scanf("%lld%lld%lld%lld", &s, &t, &d, &w);
            st[t].push_back(make_pair(-w, -d));
            ed[s].push_back(make_pair(-w, -d));
        }

        for (LL i = n; i >= 1; --i) {
            for (LL o = 0; o < (LL)st[i].size(); ++o) S.insert(st[i][o]);

            pair<LL, LL > whw = make_pair(0, 0);
            if (!S.empty()) whw = *S.begin();

            for (LL j = 0; j <= m; ++j) {
                LL hh = i + 1;
                if (whw.first) hh = -whw.second + 1;
                dp[i][j] = dp[hh][j] + (-whw.first);
                if (j) dp[i][j] = min(dp[i + 1][j - 1], dp[i][j]);
            }

            for (LL o = 0; o < (LL)ed[i].size(); ++o) S.erase(S.lower_bound(ed[i][o]));
        }

        cout << dp[1][m];

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------