CF 1562 E. Rescue Niwen! (字符串+DP+后缀数组优化)

E. Rescue Niwen!

题意：

给定一个字符串 $s$，将 $s$ 的所有子串按照它在 $s$ 中的出现位置 $l,r$排成一列，其中 $l$ 为第一关键字 $r$ 为第二关键字。
求这个字符串序列的最长上升子序列，其中大于的定义是字典序大于。

分析：

首先我们从题意中看，他要找最长上升的子序列，那么首先我们需要知道，第$x$位置开头的子序列集合我们用$S(x)$表示，那么如果我们取了第$x$位置开的的子序列那么我们取的最长上升子序列，一定是在$S(x)$中连续的。

原因：
当$x$位置元素大于前面的最长上升子序列时，那么从$x(x+1)$一定>$x$这个，然后递归下去 如果后面有位置与$x$位置元素一样，那么他后面部分位置可能会取代或者填充$S(x)$位置。

所以我们要找到这个取代或者填充的位置，那么我们就需要维护一个字符串一致的长度，直接转移过去询问。这个就是后缀数组优化。
ORZ

int dp[5100][5100];
int d[5100];
int n;
string str;
void solve()
{
    cin >> n >> str;
    str = " " + str;
    dp[n + 1][n + 1] = dp[n + 1][n] = dp[n][n + 1] = 0;
    for(int i = n; i >= 1; i--)
    {
        for(int j = n; j >= 1; j--)
        {
            if(str[i] == str[j]) dp[i][j] = dp[i + 1][j + 1] + 1; //减少复杂度，直接找到不同的地方
            else dp[i][j] = 0;
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        d[i] = n - i + 1; ///全选
        for(int j = 1; j < i; j++) ///看前面都可以选那些
        {
            int len = dp[i][j]; ///找到不同的地方
            if(i + len - 1 >= n || str[i + len] <= str[j + len]) continue;
            d[i] = max(d[i], d[j] + n - i + 1 - len);
        }
        ans = max(ans, d[i]);
    }
    printf("%d\n", ans);
}