Consecutive Subsequence

· · 个人记录

150247 Consecutive Subsequence

大致题意

给一个长度为n的序列，要从中挑出最长的连续上升的子序列（最长上升子序列）。

第一行输出最长上升子序列的长度。

第二行输出字典序最小的子序列的编号。

解

曾经学动态规划（dp）的时候学过一种题：最长上升子序列。

（最长上升子序列代码）

#include<bits/stdc++.h>
using namespace std;
int a[1005],dp[1005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int maxs=INT_MIN;
    for(int i=1;i<=n;i++){
        int maxx=0;
        for(int j=1;j<i;j++){
            if(a[i]>a[j]) maxx=max(maxx,dp[j]);
        }
        dp[i]=maxx+1;
        maxs=max(maxs,dp[i]);
    }
    cout<<maxs;
    return 0;
}

这里的dp数组指的是从a_1到a_i的最长上升子序列的最长长度。

而本题不仅要找最长长度，还要一个一个输出。

so，我们可以吧dp_i的含义改变一下，变成a_i-1的最长上升子序列长度+1（因为a_i-1+1=a_i）。

状态转移方程就从：

dp_i=max\{dp_1 \sim dp_{i-1} \}

变成：

dp_{a_i}=dp_{a_i-1}+1

又因为最长上升子序列是连续的所以我们只要知道这个序列最大值就可以知道最小值了。

所以我们可以在找最长上升子序列时找出last（last=a_i）。

first=last-max\{dp\}+1

再从1遍历到n，如果a_i=first就输出i（因为题目要输出编号，也就是下标）然后first++。

代码

#include<bits/stdc++.h>
using namespace std;
int a[200005];
map<int,int> dp;
int main(){
    int n;
    cin>>n;
    int maxl=INT_MIN,last=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[a[i]]=dp[a[i]-1]+1;
        if(maxl<dp[a[i]]){
            maxl=dp[a[i]];
            last=a[i];
        }
    }
    cout<<maxl<<endl;
    int first=last-maxl+1;
    for(int i=1;i<=n;i++){
        if(a[i]==first){
            first++;
            cout<<i<<" ";
        }
    }
    return 0;
}

最后

谢谢观看，点个赞吧。