Rescue Niwen!（字符串/dp）

题目
题意：给定一个字符串$s_1{s}_2{s}_3...s_n$，定义它的子串序列为{$s_1,s_1{s}_2,...,s_1{s}_2{s}_3...s_n,s_2,s_2{s}_3,...,s_2{s}_3...s_n,s_3,s_3{s}_4,...,s_{n-1}{s}_n，s_n$}。比如字符串$abcd$，它的子串序列为{$a,ab,abc,abcd,b,bc,bcd,c,cd,d$}，求子串序列的最长递增子序列（可以不连续）。
参考
PS：这道题标了2500，但感觉没到这个难度的样子。

思路：
1、前缀字符串一定小于原字符串。
2、预处理，计算原字符串以任意两个位置$i,j$为起点的字符串的最长公共前缀。
3、对于以$i$为起点的字符串，遍历所有起点下标$j$小于$i$的字符串，如果以$i$为起点的字符串 存在比 以$j$为起点的字符串 的串（有点绕），那么则更新小于 以$i$为起点的字符串的 子串数量。详见代码。

官方代码（写的挺好的，自己太懒 就不写了_(:з」∠)_）

#include <iostream>

using namespace std;

int16_t lcp[10000 + 5][10000 + 5];

int dp[10000 + 5];

bool is_greater(const string& s, int x, int y) {
    if (lcp[x][y] == static_cast<int>(s.size()) - x) {
        return false;
    }
    return s[x + lcp[x][y]] > s[y + lcp[x][y]];
}

int get_score(const string& s, int x, int y) {
    if (is_greater(s, x, y)) {
        return dp[y] + static_cast<int>(s.size()) - x - lcp[x][y];
    }
    return 0;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        if (s.size() != n) return 42;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                lcp[i][j] = 0;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == j) {
                    lcp[i][j] = n - i;
                } else
                if (s[i] != s[j]) {
                    lcp[i][j] = 0;
                } else {
                    lcp[i][j] = lcp[i + 1][j + 1] + 1;
                }
            }
        }
        int ans = n;
        dp[0] = n;
        for (int i = 1; i < n; i++) {
            dp[i] = n - i;
            for (int j = 0; j < i; j++) {
                dp[i] = max (dp[i], get_score(s, i, j));
            }
            ans = max(ans, dp[i]);
        }
        cout << ans << '\n';
    }
}