【洛谷 P8736】[蓝桥杯 2020 国 B] 游园安排 题解（动态规划+耐心排序+lower_bound+最长上升子序列）

[蓝桥杯 2020 国 B] 游园安排

题目描述

$\mathrm{L}$ 星球游乐园非常有趣，吸引着各个星球的游客前来游玩。小蓝是 $\mathrm{L}$ 星球 游乐园的管理员。

为了更好的管理游乐园，游乐园要求所有的游客提前预约，小蓝能看到系统上所有预约游客的名字。每个游客的名字由一个大写英文字母开始，后面跟 $0$ 个或多个小写英文字母。游客可能重名。

小蓝特别喜欢递增的事物。今天，他决定在所有预约的游客中，选择一部分游客在上午游玩，其他的游客都在下午游玩，在上午游玩的游客要求按照预约的顺序排列后，名字是单调递增的，即排在前面的名字严格小于排在后面的名字。

一个名字 $A$ 小于另一个名字 $B$ 是指：存在一个整数 $i$，使得 $A$ 的前 $i$ 个字母与 $B$ 的前 $i$ 个字母相同，且 $A$ 的第 $i+1$ 个字母小于 $B$ 的第 $i+1$ 个字母。(如果 $A$ 不存在第 $i+1$ 个字母且 $B$ 存在第 $i+1$ 个字母, 也视为 $A$ 的第 $i+1$ 个字母小于 $B$ 的第 $i+1$ 个字母)

作为小蓝的助手，你要按照小蓝的想法安排游客，同时你又希望上午有尽量多的游客游玩，请告诉小蓝让哪些游客上午游玩。如果方案有多种，请输出上午游玩的第一个游客名字最小的方案。如果此时还有多种方案，请输出第一个游客名字最小的前提下第二个游客名字最小的方案。如果仍然有多种，依此类推选择第三个、第四个……游客名字最小的方案。

输入格式

输入包含一个字符串，按预约的顺序给出所有游客的名字，相邻的游客名字之间没有字符分隔。

输出格式

按预约顺序输出上午游玩的游客名单，中间不加任何分隔字符。

样例 #1

样例输入 #1

WoAiLanQiaobei

样例输出 #1

AiLanQiaobei

提示

对于 $20\%$ 的评测数据, 输入的总长度不超过 $20$ 个字母。

对于 $50\%$ 的评测数据, 输入的总长度不超过 $300$ 个字母。

对于 $70\%$ 的评测数据, 输入的总长度不超过 $10000$ 个字母。

对于所有评测数据, 每个名字的长度不超过 $10$ 个字母, 输入的总长度不超过 $10^6$ 个字母。

蓝桥杯 2020 年国赛 B 组 G 题。

思路

如果用两层循环进行动态规划，部分测试点报TLE。可以用二分搜索优化时间复杂度。

首先从输入中读取所有游客的名字，游客的名字由一个大写字母开始，后面跟随0个或多个小写字母，因此，当读取到大写字母时，将其作为新的名字；当读取到小写字母时，将其添加到当前名字的末尾。

定义了一个名为 dp 的字符串数组，用于存储长度为 i 的递增序列的最小末尾元素。同时，定义了一个名为 ans 的字符串数组，用于存储长度为 i 的递增序列的所有元素。

对于每个名字，找到 dp 中第一个大于或等于当前名字的位置 pos，然后更新 dp[pos] 为当前名字，ans[pos] 为 ans[pos-1] 和当前名字的拼接。

最后输出 ans[len]，其中 len 是最长递增子序列的长度，即上午游玩的游客数量最多的情况。

AC代码

#include <algorithm>
#include <cmath>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;

int n = 0;
char c;
string s[N], dp[N], ans[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	while (cin >> c) {
		if (isupper(c)) {
			s[++n] = c;
		} else {
			s[n] += c;
		}
	}

	int len = 0;
	for (int i = 1; i <= n; i++) {
		int pos = lower_bound(dp + 1, dp + len + 1, s[i]) - dp;
		len = max(len, pos);
		dp[pos] = s[i];
		ans[pos] = ans[pos - 1] + s[i];
	}
	cout << ans[len] << "\n";
	return 0;
}