Music Festival

Created by LXC on Sun Oct 8 09:32:15 2023

https://codeforces.com/problemset/problem/1801/C

ranting: 1900

tag: binary search, data structures, dp, greedy, sortings

problem

给出n张专辑，每张专辑中有不同数目的歌曲，每首歌曲都有一个cool值。

每张专辑只能顺序播放，不能调整歌曲的顺序。

当听到一首歌曲的cool值比之前所有听过的都大，则增加一点印象值。

现在，你需要将专辑调整播放顺序，使得印象值最大。

solution

首先对于每张专辑都可以进行预处理。每张专辑的cool值都可以成为单调增长的。

cool值的值域很大，我们将其离散化。

对于已经预处理，离散化的第i张专辑有$k_i$首歌曲，$a_{i, 1},\ a_{i, 2},\ a_{i, 3},\ \ldots,\ a_{i, k_i}$。

设$f_x$为cool值小于等于x的最大印象值。显然有$f_{x} = max(f_{x}, f_{x-1})$

对于专辑i中如果cool值小于$a_{i,j}$的都已经听过，那么第i张专辑的贡献为$f_{a_{i,k_i}} = f_{a_{i,j}-1} + k_i-j+1$

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<vector<int>> a(n);
    map<int, int> id;
    for (int i = 0; i < n; i++) {
        int k, mx = 0;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int x;
            cin >> x;
            if (x > mx) {
                a[i].push_back(x);
                id[x];
                mx = x;
            }
        }
    }
    // for (auto& i : a) {
    //     for (auto& j : i) {
    //         cout << j << " ";
    //     }
    //     cout << endl;
    // }
    int sz = 0;
    for (auto& [i, j] : id) {
        j = ++sz;
        // cout << i << " -- " << j << "\n";
    }

    map<int, vector<pair<int, int>>> mp;
    for (auto& i : a) {
        int isz = i.size();
        for (int j = 0; j < isz; j++) {
            mp[id[i[j]]].emplace_back(id[i.back()], isz - j);
        }
    }
    vector<int> dp(sz + 1);
    for (int i = 1; i <= sz; i++) {
        for (auto& [x, y] : mp[i]) {
            dp[x] = max(dp[x], dp[i - 1] + y);
        }
        dp[i] = max(dp[i - 1], dp[i]);
    }
    // for (int i = 0; i <= sz; i++) {
    //     cout << dp[i] << ", ";
    // }
    cout << dp[sz] << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}