CF1562E
BBD186587
·
·
题解
首先，容易发现，s[i,j+1] 的字典序一定大于 s[i,j]，所以，s[i,j] 后面一定能接上 s[i,j+1]。
有一个结论，一定存在一种答案最优的选择方案，使得，若 s[i,j] 被选了，则 s[i,j+1 \sim n] 也被选。下面证明这个结论。
假设 s[i,j \sim k] 全都选了，s[i,k+1] 忽然不选了。考虑在什么情况下才会导致这样改变选择。显然，一定存在一对 l,r，使得 l>i 且 s[l,r] > s[i,k] 且 s[l,r] < s[i,k+1]。
首先，一定有 s[l,r-1]=s[i,k]。
若 s[l,r-1]<s[i,k]，则显然在 k 更小的时候就可以改变选择了，得到的答案一定不会比现在劣。若 s[l,r-1]>s[i,k]，则一定有 s[l,r]>s[i,k+1]。不满足定义的条件。
既然如此，选 s[i,k] 就可以视作是选了 s[l,r-1]，并从 s[l,r] 开始继续往后选。可以把这个理解为一个“继承”的过程，一定会不断“继承”，直到选上了一个 s[x,n]（否则，答案一定不优）。总的来看，就可以认为我们选择了 s[x,y \sim n]。
这样一个“继承”的过程就包含了所有可能会使答案更优的改变选择的情况，至此，结论证毕。所以，只需考虑所有以 s[i,n] 为结尾的 LIS 即可。
令 \operatorname{lcp}(i,j) 表示满足 s_{i+k} 与 s_{j+k} 不相等的最小的 k，令 f_i 表示以 s[i,n] 为结尾的 LIS。
若 s_{i+\operatorname{lcp}(i,j)}>s_{j+\operatorname{lcp}(i,j)}，则 f_i 是可以由 f_j 转移过来的，转移为：f_i=(n-i+1)+\max \limits_{1 \leq j <i}\{f_j-\operatorname{lcp}(i,j)\}。
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=5010;
int T,n,f[N];
int lcp[N][N];
char s[N];
int MAX(int x,int y)
{
return x>y?x:y;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
scanf("%s",s+1);
for(int i=1;i<n;i++)
lcp[i][n]=(s[i]==s[n]);
for(int j=n-1;j>=1;j--)
for(int i=j-1;i>=1;i--)
{
if(s[i]==s[j]) lcp[i][j]=lcp[i+1][j+1]+1;
else lcp[i][j]=0;
}
for(int i=1;i<=n;i++) f[i]=n-i+1;
for(int i=2;i<=n;i++)
for(int j=1;j<i;j++)
if(s[i+lcp[j][i]]>s[j+lcp[j][i]])
f[i]=MAX(f[i],f[j]+n-i+1-lcp[j][i]);
int ans=0;
for(int i=1;i<=n;i++) ans=MAX(ans,f[i]);
printf("%d\n",ans);
}
return 0;
}
```