专栏文章

题解：P14040 [PAIO 2025] Exhibition

__cbw
P14040题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minmz6yr
此快照首次捕获于
2025/12/02 05:03
3 个月前
此快照最后确认于
2025/12/02 05:03
3 个月前
查看原文

Solution

设 bisect⁡(T,v)\operatorname{bisect}(T, v) 表示 nn 个元素的列表 TT 中第一个大于等于 vv 的元素的位置，下标从 00 开始。若 max⁡T<v\max T < v 则为 nn（相当于 lower_bound）。
先不考虑第一个条件。
两维不好做，考虑先按 BiB_i 从小到大排个序。题目转化为求关于 AiA_i 的最长不下降子序列，使用 Θ(Nlog⁡N)\Theta(N \log N) 的算法 可以解决。
现在考虑加上限制。SS 从小往大尽可能取显然最优，所以先将 SS 排序。额外维护一个 pp 数组，表示长度为 ii 的最长上升子序列最少需要取到 S0,1,⋯ ,piS_{0, 1, \cdots, p_i}。
更新时，设原来算法二分出的位置是 xx，则更新 px=max⁡{px−1+1,bisect⁡(S,Ax)}p_x = \max\{p_{x - 1} + 1, \operatorname{bisect}(S, A_x)\}。第一项加 11 是因为不能重复选画框。
若 px≥Mp_x \ge M（注意 0-base），表示没有合适的画框，不进行更新。否则执行原来算法的更新。

Code

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...