题解：P14040 [PAIO 2025] Exhibition

· · 题解

Solution

设 \operatorname{bisect}(T, v) 表示 n 个元素的列表 T 中第一个大于等于 v 的元素的位置，下标从 0 开始。若 \max T < v 则为 n（相当于 lower_bound）。

先不考虑第一个条件。

两维不好做，考虑先按 B_i 从小到大排个序。题目转化为求关于 A_i 的最长不下降子序列，使用 \Theta(N \log N) 的算法 可以解决。

现在考虑加上限制。S 从小往大尽可能取显然最优，所以先将 S 排序。额外维护一个 p 数组，表示长度为 i 的最长上升子序列最少需要取到 S_{0, 1, \cdots, p_i}。

更新时，设原来算法二分出的位置是 x，则更新 p_x = \max\{p_{x - 1} + 1, \operatorname{bisect}(S, A_x)\}。第一项加 1 是因为不能重复选画框。

若 p_x \ge M（注意 0-base），表示没有合适的画框，不进行更新。否则执行原来算法的更新。

Code

#include "exhibition.h"
#include <algorithm>
#include <utility>
#include <vector>
#define MAXN 100003
#define IMX 0x3f3f3f3f
using namespace std;

int max_paintings(int N, int M, vector<int> A, vector<int> B, vector<int> S)
{
    pair<int, int> a[MAXN];
    int dp[MAXN], pos[MAXN];
    int i, tmp;
    for (i = 0; i < N; ++i)
        a[i] = {B[i], A[i]};
    sort(a, a + N), sort(S.begin(), S.end());
    dp[0] = 0, fill(dp + 1, dp + N + 1, IMX);
    pos[0] = -1;
    for (i = 0; i < N; ++i)
    {
        tmp = (int)(upper_bound(dp + 1, dp + N + 1, a[i].second) - dp);
        pos[tmp] = max(pos[tmp - 1] + 1, (int)(lower_bound(S.begin(), S.end(), a[i].second) - S.begin()));
        if (pos[tmp] >= M)
            continue;
        dp[tmp] = a[i].second;
    }
    for (i = N; dp[i] == IMX; --i)
        ;
    return i;
}