做题时间：2022.9.22
\(【题目描述】\)
多组数据，每组数据给定一个字符串 \(s(|s|\leq 5000,\sum |s|\leq 10^4)\)，将 \(s\) 的所有子串排序，按照在 \(s\) 中出现的位置 \(l,r\)，其中 \(l\) 为第一关键字，\(r\) 为第二关键字。求这个字符串序列的最长上升子序列。
\(【输入格式】\)
第一行一个 \(T\) 表示数据组数
每组数据第一行一个 \(n\) 表示字符串长度
第二行一个字符串 \(s\)
\(【考点】\)
字符串、dp
\(【做法】\)
可以类比一下求普通LIS，定义 \(f_{l,r}\) 表示以 \(s[l,r]\) 为结尾的序列的LIS，发现状态数过多。进而发现有：\(s[i,i]<s[i,i+1]<...<s[i,n]\)，也就是说若 \(s[i,j]\) 被选入LIS，那么其后一直到 \(s[i,n]\) 都将被选入。因此只需要考虑 \(s[i,n]\) 的选入情况即可。定义 \(f_i\) 表示以 \(s[i,n]\) 为结尾的LIS长度。比较串 \(s[i,n]\) 和 \(s[j,n]\) 时直接比较 \(s[i+lcp_{i,j}]\) 和 \(s[j+lcp_{i,j}]\) 即可。有：
\[ f_i=\max\left\{ \begin{array}{rcl} n-i+1\\ f_j-lcp_{i,j}-i+1 & s_j<s_i\\ \end{array} \right. \]然后 \(O(n^2)\) 预处理 \(lcp_{i,j}\) 即可。
\(【代码】\)
#include<cstdio>
#include<iomanip>
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+50;
int f[N],lcp[N][N],t,n;
char s[N];
inline void init()
{
for(int i=n;i>=1;i--){
for(int j=n;j>=1;j--){
if(s[i]==s[j]) lcp[i][j]=lcp[i+1][j+1]+1;
else lcp[i][j]=0;
}
}
}
inline int solve()
{
int maxn=0;
for(int i=1;i<=n;i++){
f[i]=n-i+1;
for(int j=1;j<i;j++){
if(lcp[i][j]==n-j+1||s[j+lcp[i][j]]<s[i+lcp[i][j]]) f[i]=max(f[i],f[j]+n-i-lcp[i][j]+1);
}
maxn=max(maxn,f[i]);
}
return maxn;
}
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d%s",&n,s+1);
init();
printf("%d\n",solve());
}
return 0;
}