这里不再讲述模板，讲讲变形

1.最大字典序最长上升子序列

题目

对数列 $a$，它的上升子序列指的是形如 $a_{p_1}…a_{p_k}$ ，且满足 $0 < p_1 < \dots p_k$ 和 $a_{p_1} < \dots a_{p_k}$ 的序列 。

求出最长上升子序列的长度，并输出其中字典序最大的一个。

思路

这道题其实是普通模板中的变形。

考虑普通转移式：$f_i = \min(f_i,f_j+1)$，我们可以就在这个式子上面做改变。

设 $g_i$ 表示满足比 $a_i$ 小且在以 $i$ 结尾的最长上升子序列的方案中的最大的数的下标。

举个例子：1 4 2 3
对于 $3$,它的 $g$ 对应的就是 $2$，即有：$g_4=3$

此时，我们分两种情况：
1. $f_i<f_j+1$：
有：$f_i=f_j+1$，$g_i=j$
因为当前找出了最长的一段，就一定要更新。
2. $f_i=f_j+1$
有：$g_i = \max(g_i,j)$
相同的话就与先前求出的做一个比较。

最后找出结尾，跑一遍递归即可

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=2e5+10;
int n;
int a[N];
int f[N],g[N];
int ans[N],cnt;
void dfs(int u){
    if(!u){
        return;
    }
    ans[++cnt]=a[u];
    dfs(g[u]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        f[i]=1;
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[j]<a[i]){
                if(f[i]<f[j]+1){
                    f[i]=f[j]+1;
                    g[i]=j;
                }else if(f[i]==f[j]+1){
                    if(a[g[i]]<a[j]){
                        g[i]=j;
                    }
                }
            }
        }
    }
    int res1=0,res2=0;
    for(int i=1;i<=n;i++){
        if(f[i]>res1){
            res1=f[i],res2=i;
        }else if(f[i]==res1){
            if(a[res2]<a[i]){
                res2=i;
            }
        }
    }
    cout<<res1<<endl;
    dfs(res2);
    for(int i=cnt;i;i--){
        cout<<ans[i]<<' ';
    }
}