博客

题意:

现在有一个空队列 Q 以及 N 个数字需要按顺序插入，你可以选择插入队列的头部或尾部，请问在合理选择插入方式的前提下，插入后的队列的最长上升子序列的长度最大是多少？

最长上升子序列指的是在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。子序列指的是通过删除原序列中零个或多个元素后获得的序列。

输入第一行是一个数 N (1≤N≤1000)，表示有 N 个要按顺序插入的数字。

接下来一行 N 个数，表示要插入的数字，数字已经按插入顺序排列好，并且都在 32 位整数范围内。

输出两行，第一行是一个数字，表示最大的最长上升子序列的长度。

接下来一行，输出插入的方案，其中用

L

表示插入到头部，用

R

表示插入到尾部。当有多个相同长度的方案时，选择

字典序最小

的方案（L 的字典序小于 R）。

分析:

用双端队列来找最长上升子序列，且字典序最小。

数据范围为1000，最高可以

，可以暴力枚举r的第一个点作为起点，通过上升子序列，找出来，最后求出字典序最小的。

样例:

输入:

8
1 3 2 4 2 4 5 0

输出:

5
LLLLLRRL

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

typedef long long ll;
ll g1[N];
ll a[N];
ll f[N];
ll res = 0;
ll st[N];
ll f2[N];
vector<int> g;
int 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];
                }
            }
        }
        ll cnt = len;
        int len1 = 0;
        for (int j = n; j; j--) {
            if (g1[j] == cnt && cnt) s.push_back(j), cnt--;
            g1[j]=0;
        }
        sort(s.begin(), s.end());
        for (int j = 0; j < s.size(); j++) st[s[j]] = 1;
        ll 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;
}