⭐️前面的话⭐️

本篇文章介绍来自2020年蓝桥杯真题之游园安排，算法考察动态规划，最长上升子序列，线性DP，序列记录，二分（没想到，暂没更新），展示语言java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2023年4月7日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

⭐️游园安排⭐️

🔐题目详情

游园安排

💡解题思路

本质上是一个最长上升子序列的问题，长度比较好求，难点在于记录题目要求的最长序列，可以使用pre数组记录每个上升子序列最后一个字符串的前一个字符串，再枚举出最大长度和字典序最小的序列最后一个字符串的下标，就能通过pre逆推出字典序最小的序列。

🔑源代码

最长上升子序列，暴力枚举（70分）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = (int) 1e6 + 10;
//记录最长上升子序列长度
int f[N];//记录以第i个字符串结尾的最长上升子序列的前一个位置
int pre[N];
string s;
string ss[N];
string ans[N];bool is_big(string s1, string s2) 
{int minn = min(s1.size(), s2.size());for (int i = 0; i < minn; i++) {if (s1[i] != s2[i]) return s1[i] > s2[i];}return s1.size() > s2.size();
}int main() 
{cin >> s;int n = s.size();int idx = 0;for (int i = 0; i < n; i++) { if (s[i] >= 'A' && s[i] <= 'Z') {int j = i + 1;while (j < n && s[j] >= 'a' && s[j] <= 'z') j++;ss[++idx] = s.substr(i, j - i);i = j  - 1;}}int m = idx;//最长上升子序列int maxLen = 0;int last = 0;for (int i = 1; i <= m; i++) {f[i] = 1;for (int j = 1; j < i; j++) {if (is_big(ss[i], ss[j]) && f[j] + 1 > f[i]){f[i] = f[j] + 1;pre[i] = j;}if (is_big(ss[i], ss[j]) && f[j] + 1 == f[i]) {if (is_big(ss[pre[i]], ss[j])) {pre[i] = j;}}}if (maxLen < f[i]) {maxLen = f[i];last = i;}if (maxLen == f[i]) {if (is_big(ss[last], ss[i])) last = i;}}//逆序输出上升子序列idx = maxLen - 1;while (last != 0) {ans[idx--] = ss[last];last = pre[last];}//cout << is_big("T","Szr") << endl;for (string x : ans) cout << x;cout << endl;return 0;
}

🌱总结

过了70%，二分不会。