Rescue Niwen!（字符串/dp）

题目 题意：给定一个字符串 s 1 s 2 s 3 . . . s n s_1s_2s_3...s_n s1​s2​s3​...sn​，定义它的子串序列为{ 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 s_1,s_1s_2,...,s_1s_2s_3...s_n,s_2,s_2s_3,...,s_2s_3...s_n,s_3,s_3s_4,...,s_{n-1}s_{n}，s_n s1​,s1​s2​,...,s1​s2​s3​...sn​,s2​,s2​s3​,...,s2​s3​...sn​,s3​,s3​s4​,...,sn−1​sn​，sn​}。比如字符串 a b c d abcd abcd，它的子串序列为{ a , a b , a b c , a b c d , b , b c , b c d , c , c d , d a,ab,abc,abcd,b,bc,bcd,c,cd,d a,ab,abc,abcd,b,bc,bcd,c,cd,d}，求子串序列的最长递增子序列（可以不连续）。 参考 PS：这道题标了2500，但感觉没到这个难度的样子。

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

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

#include 

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(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(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 = 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