Codeforces Round #741 (Div. 2) E. Rescue Niwen! 字符串 + dp

传送门

题意：

给你一个串$s$，定义其扩张串为$s_1,s_1{s}_2,...,s_1{s}_2..s_n,s_2,s_2{s}_3,...,s_n$，现在让你从扩张串中选一个最长上升子序列，按照字典序大小比较。

$n\le 5000$

思路：

首先，可以发现，当选择一个后缀串$s$，由于$s$的前缀都在$s$的前面，那么$s$的所有前缀都可以加入答案中(当合法的时候)，那么可以定义状态$dp[i]$表示以$i$的后缀为结尾的最长上升子序列，初始$dp[i]=n-i+1$。

转移的时候显然可以直接从$[1,i-1]$转移过来，当前面一个串为$ababd$，当前串$abd$，$ababd<abd$，显然是可以直接转移过来的，考虑对答案的贡献是多少，按照上面说的$n-i+1$是算上了$abd$所有前缀串，但是$a,ab$显然是不合法的，原因就是他与前面$ababd$的前缀串重复了，所以我们要减去两个的最长公共前缀，由于我们是按照字典序严格递增来转移的，所以重复的只有最长公共前缀这一块，并不会与前面已经转移的状态冲突，直接算的话复杂度$O(n^3)$，考虑预处理一下。

定义$f[i][j]$表示分别以$i,j$为后缀起点的串的最长公共前缀，由于枚举的是后缀，所以可以倒着来转移，转移方程$f[i][j]=(f[i+1][j+1]+1)\ast (s[i]==s[j])$，与最长公共前缀还是有区别的。

求出来$f$，那么$dp$转移也比较明显了，转移方程$dp[i]=max(dp[i],dp[j]+n-i+1-f[i][j])$，当然转移前提是$s[i+f[i][j]]>s[j+f[i][j]]$。

// Problem: E. Rescue Niwen!
// Contest: Codeforces - Codeforces Round #741 (Div. 2)
// URL: https://codeforces.com/contest/1562/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std;

//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }
//void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }
//void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

const int N=5010,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;

int n;
int f[N][N],dp[N];
char s[N];

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
	
	int _; scanf("%d",&_);
	while(_--) {
		scanf("%d%s",&n,s+1);
		f[n+1][n+1]=f[n+1][n]=f[n][n+1]=0;
		for(int i=n;i>=1;i--) {
			for(int j=n;j>=1;j--) {
				if(s[i]==s[j]) f[i][j]=f[i+1][j+1]+1;
				else f[i][j]=0;
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++) {
			dp[i]=n-i+1;
			for(int j=1;j<i;j++) {
				int len=f[i][j];
				if(i+len-1>=n||s[i+len]<=s[j+len]) continue;
				dp[i]=max(dp[i],dp[j]+n-i+1-len);
			}
			ans=max(ans,dp[i]);
		}
		printf("%d\n",ans);
	}



	return 0;
}
/*

*/