题意:
用双端队列来找到最长的上升子序列,并且字典序最小
分析
根据数据范围 \(1000\) 可以发现在可以\(n^2logn\),那我们就可以暴力枚举r开始的第一个点作为起点,通过上升子序列,找出来,最后求出字典序最小的即可
代码
/*made in mrd*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define int long long
#define mem(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define lu u << 1
#define ru u << 1 | 1
#define pb push_back
#define bug1(x) cout << x << endl
#define bug2(x, y) cout << x << ' ' << y << endl
#define pii pair<int, int>
#define bug3(x, y, z) cout << x << ' ' << y << ' ' << z << endl
int g1[N];
int a[N];
int f[N];
int res = 0;
int st[N];
int f2[N];
vector<int> g;
signed main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n + 1; i++) {
vector<int> s;
int len = 0;
for (int j = i; j <= n; j++) {
if (!len)
f[++len] = a[j], g1[j] = len;
else {
if (f[len] < a[j] && a[j] > f[1])
f[++len] = a[j], g1[j] = len;
else if (a[j] > f[1]) {
int x = lower_bound(f + 1, f + len + 1, a[j]) - f;
g1[j] = x;
f[x] = a[j];
}
}
}
int cnt = len;
int len1 = 0;
for (int j = n; j; j--) {
if (g1[j] == cnt && cnt) s.pb(j), cnt--;
g1[j]=0;
}
sort(s.begin(), s.end());
for (int j = 0; j < s.size(); j++) st[s[j]] = 1;
int x = f[1];
if (len == 0) x = 1e18;
for (int j = n; j ; j--) {
if (st[j]) {
st[j] = 0;
continue;
}
if (!len1 && a[j] <x)
f[++len1] = a[j];
else if (a[j] < x) {
if (a[j] > f[len1])
f[++len1] = a[j];
else {
int x = lower_bound(f + 1, f + len1 + 1, a[j]) - f;
f[x] = a[j];
}
}
}
if (len + len1 > res)
g = s, res = len + len1;
else if (len + len1 == res) {
if(g.size()==0) continue;
if (s.size() == 0) {
g = s;
} else if (s > g)
g = s;
}
}
for (int i = 0; i < g.size(); i++) {
st[g[i]] = 1;
}
cout << res << endl;
for (int i = 1; i <= n; i++) {
if (st[i])
cout << "R";
else
cout << "L";
}
return 0;
}