CF977F 题解

· · 题解

题目传送门

题目描述

输入一个数 n ，接下来输入 n 个数 a_1 至 a_n ，要求最长递增子序列的长度以及这个子序列每一个元素的值。

很明显，这道题要分成两问来看。

第一问，求最长递增子序列的长度

相信你在看到这一问时一定很懵。 不懵就不会来看我的题解了

那么，就让我们想一想，和这一问相似的问题有哪些？

没错，就是求最长上升子序列的长度。

在做 求最长上升子序列 这个问题时，我们从 a_1 到 a_n 循环了一遍，对于第 i 位的 a_i ，我们都求出了以 a_i 为结尾的最长上升子序列的长度。

那么，这一问的求法自然而然就是：

从 a_1 到 a_n 循环一遍，对于第 i 位的数字 a_i ,都求出以 a_i 为结尾的最长递增子序列的长度。

最后取记录答案的数组 dp ，取 dp 数组的最大值即可。

代码：


for (int i=1;i<=n;i++){
    cin>>a[i];

    int f=m[a[i]-1];
    if (f>0)
        dp[i]=dp[f]+1;
    else
        dp[i]=1;
    m[a[i]]=i;
    }

for (int i=1;i<=n;i++)
    if (num<dp[i])
        num=dp[i];

注：这里之所以要用 map 是因为要快速查找 / 删除元素，而这一切都符合 map 的特性。

第二问，求这个递增子序列的每一个元数的值

要想求出这些元素的值，我们就要利用递增子序列的特性：

  1. 对于这个递增子序列的除开头外的每一位，它都必定等于它的前一位 +1 。

  2. 因为 1 ，所以这个递增子序列的第一位的值就必定是最后一位的值 cnt 减这个序列的长度 num 再加 1 。

所以我们只需要在运行第一位的时候记录递增子序列的最后一位，再暴力求元素即可。

代码：

num=cnt-num+1;
for (int i=1;i<=n;i++)
    if (a[i]==num){
        cout<<i<<" ";
        num++;
    }

AC code 

#include <bits/stdc++.h>

using namespace std;

int n, num, cnt;
int a[200005], dp[200005];
map < int, int> m;

void fun1 (){
    for (int i=1;i<=n;i++)
        if (num<dp[i])
            num=dp[i];
}
//处理第一问

void fun2 (){
    num=cnt-num+1;
    for (int i=1;i<=n;i++)
        if (a[i]==num){
            cout<<i<<" ";
            num++;
        }
    cout<<endl;
}
//处理第二问。

int main (){
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];

        int f=m[a[i]-1];
        if (f>0)
            dp[i]=dp[f]+1;
        else
            dp[i]=1;
        m[a[i]]=i;
    }

    num=-1;
    fun1 ();
    cout<<num<<endl;

    fun2 ();

    return 0;
}

end.