F. Music Festival

题目连接

题目大意：给你 N N N 个舞台，每个舞台上有 M M M 个节目，每个节目有三个信息： ( s , e , w ) (s, e, w) (s,e,w) 分别代表开始时间，结束时间和看这个节目所获得的权值。现在问，在每个舞台至少都看一场节目的前提下，我们所能获得的最大权值是多少，若前提都无法满足，则输出 − 1 -1 −1 。

解：

因为舞台只有 10 10 10 个，我们考虑用状压 D P DP DP 解决这个问题。我们设 D P DP DP 数组 d p [ i ] [ j ] dp[i][j] dp[i][j] 的含义为：时间为 i i i ，舞台状态为 j j j 所能获得的最大权值，即最终答案为 d p [ 全 局 最 晚 结 束 的 节 目 的 时 间 ] [ ( 1 < < N ) − 1 ] dp[全局最晚结束的节目的时间][(1<<N) - 1] dp[全局最晚结束的节目的时间][(1<<N)−1] 。我们现在可以用类似背包的思想去更新状态，对于 d p [ i ] [ j ] dp[i][j] dp[i][j] 而言，有两种情况，要么没在看节目，要么第 i i i 秒在看节目（这个节目肯定在第 i i i 秒结束）。对于第一种情况而言，那么 d p [ i ] [ j ] dp[i][j] dp[i][j] 自然就等于 d p [ i − 1 ] [ j ] dp[i - 1][j] dp[i−1][j] 。第二种情况的话，我们就可以遍历所有结束时间在 i i i 的节目（一开始存节目的时候就用结束时间当下标存储），然后首先这个节目在状态 j j j 中肯定得为 1 1 1 ，不然不能看这个节目。在满足条件后，对于某个节目 k k k 来说，我们设可以转移到 d p [ i ] [ j ] dp[i][j] dp[i][j] 的状态为 d p [ x ] [ y ] dp[x][y] dp[x][y] ，那么显然 x = k 节 目 的 开 始 时 间 x=k节目的开始时间 x=k节目的开始时间（因为我们肯定希望转移的时间越晚越好，这样时间越多权值才会越大，但是再晚也不能晚过 k k k 节目的开始表演时间）， y y y 只有两种情况，即在 x x x 时， k k k 节目所属的舞台还没访问过， 或者访问过。那么总共也就是两种情况，对于这两种情况取 M A X MAX MAX 再加上 k k k 节目的权值就是 d p [ i ] [ j ] dp[i][j] dp[i][j] 在第 i i i 秒看节目 k k k 的最大值了（每情况要合理才能加上 k k k 节目权值，不然要设置为 − 1 -1 −1 ），那么我们最后就在每个在 i i i 时刻结束的节目取到 M a x Max Max 了，然后再和 d p [ i − 1 ] [ j ] dp[i - 1][j] dp[i−1][j] 取一个最大值就是 d p [ i ] [ j ] dp[i][j] dp[i][j] 的答案了。最后注意对 d p [ 0 ] [ j ] dp[0][j] dp[0][j] 的初始化

#include <bits/stdc++.h>

using namespace std;

const int N = 10;
const int T = 86400 + 7;

struct Stage {
    int s;
    int w;
    int id;
};
int n, dp[T][(1 << N) + 2], Max;
vector<Stage> stg[T];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int len; 
        scanf("%d", &len);
        while(len--) {
            int s, e, w;
            scanf("%d%d%d", &s, &e, &w);
            stg[e].push_back({s, w, i});
            Max = max(Max, e);
        }
    }
    int limit = (1 << n);
    for (int j = 1; j < limit; ++j) dp[0][j] = -1;
    for (int i = 1; i <= Max; ++i) {
        for (int j = 0; j < limit; ++j) {
            dp[i][j] = dp[i - 1][j];
            for (int k = 0; k < stg[i].size(); ++k) {
                if (!(j & (1 << stg[i][k].id))) continue;
                int pre_t = stg[i][k].s, pre_s = j - (1 << stg[i][k].id), m1 = -1, m2 = -1;
                if (dp[pre_t][j] != -1) m1 = dp[pre_t][j] + stg[i][k].w;
                if (dp[pre_t][pre_s] != -1) m2 = dp[pre_t][pre_s] + stg[i][k].w;
                dp[i][j] = max(dp[i][j], max(m1, m2));
            }
        }
    }
    printf("%d", dp[Max][(1 << n) - 1]);
}