Zzzzzzz

从数据范围可以知道，最多有1e6个单词，用普通的n^2写法只能拿到70%的分数，显然，要拿到全部的分数，需要用二分优化的写法，并且该题需要输出方案，一般的dp问题输出方案，都是倒序从最终态往最初态逆推，但是该题的二分写法不需要用到状态数组，我们需要一个记录状态的数组record，其中record[i]表示当前位置i是长度为r + 1的上升子序列的最后一个字符串的下标（从0开始），然后我们从最长的LIS长度开始往前逆推即可。

## C++代码
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1000010;

string s;
int record[N], n;
string p[N];
string strs[N];

int main() {
    cin >> s; s += 'A';
    for(int i = 0, prev = -1; i < s.size(); i ++) {
        char c = s[i];
        if(c >= 'A' && c <= 'Z') {
            if(prev != -1) strs[n ++ ] = s.substr(prev, i - prev);
            prev = i;
        }
    }

int len = 0;
    for(int i = 0; i < n; i ++) {
        string t = strs[i];
        int l = 0, r = len;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if(p[mid] < t) l = mid;
            else r = mid - 1;
        }

if(p[r] >= t) continue;

p[r + 1] = t;
        len = max(len, r + 1);
        record[i] = r + 1; // 当前位置i是长度为r + 1的上升子序列的最后一个字符串的下标
    }

vector<string> res;
    for(int i = n - 1; i >= 0; i --) {
        if(len <= 0) break;
        if(record[i] == len) {
            res.push_back(strs[i]);
            len -- ;
        }
    }

for(int i = res.size() - 1; i >= 0; i --) cout << res[i];
    return 0;
}
```

0.0分

0 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

Zzzzzzz

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

用筛法求之N内的素数。（C++代码）

A+B for Input-Output Practice (III) （C语言代码）

LIS二分优化 + 倒序输出方案（C++）

评论区

精彩推荐

【求帮助】C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言训练-自守数问题（C语言代码） long long

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

蛇行矩阵（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

Zzzzzzz

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

用筛法求之N内的素数。 （C++代码）

A+B for Input-Output Practice (III) （C语言代码）

LIS二分优化 + 倒序输出方案 （C++）

评论区

精彩推荐

【求帮助】C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言训练-自守数问题 （C语言代码） long long

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

蛇行矩阵 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

用筛法求之N内的素数。（C++代码）

LIS二分优化 + 倒序输出方案（C++）

　　评论区

C语言训练-自守数问题（C语言代码） long long

C语言考试练习题_一元二次方程（C语言代码）

蛇行矩阵（C语言代码）