Codeforces 1562E Rescue Niwen!

思路

对于字符串 $s_1{s}_2{s}_3...s_n$

我们先来考虑一个子集，仅讨论以 $s_1,s_2$ 两个位置为开头的扩展字符串列中的最长递增子序列，即 $s_1;...;s_1,...,s_n;s_2;...;s_2...s_n$ 中的最长递增子序列

情况一：$s_1>s_2$

显然，此时 $s_1,s_2$ 只能二则择一，即，要么选 $s_1$ 为开头的扩展字符串集合作为答案，要么选 $s_2$ 的

情况二：$s_1<s_2$

显然，此时应该贪心的都选

情况三：$s_1=s_2$

那么我们继续来考虑各自的下一位，即 $s_{1+1}=s_2$ 和 $s_{1+2}=s_3$ 的关系

如果 $s_2=s_3$ ，继续考虑各自的下一位，即 $s_3$ 和 $s_4$ 的关系

如果 $s_2<s_3$ ，那么类似情况二，可以贪心选完 $s_1$ 开头的，再从 $s_2$ 开头且到了 $s_3$ 的开始选到最后

举个例子，假设串是 $aaabbc$ ，那么只考虑前两个位置为开头扩展出来应该是 $1a$ , $2aa$ , $3aaa$ , $4aaab$ , $5aaabb$ , $6aaabbc$ , $7a$ , $8aa$ , $9aab$ , $10aabb$ , $11aabbc$

那么此时 $s_1=s_2$ 且 $s_2=s_3$ ，然后 $s_3<s_4$ ，那么首先贪心选 $s_1$ 开头的，于是选了 1 2 3 4 5 6 ，然后从 $s_2$ 开头且到 $s_4$ 的开始选，于是选了 9 10 11

怎么说明是最优呢，显然对于相等的字符串，是肯定要贪心选择位置更小的，而对于前面相等的位置，选 1 肯定比选 7 优，选 2 肯定比 选 8 优，

所以前面相等的部分不用再考虑，对于不相等的部分这种贪心策略能达到可选的最大值

如果 $s_2>s_3$ ，首先，对于前面相等的部分是不用考虑的，亦如上述

对于不相等的部分，容易发现选了一边就无法再选另一边了

综上，设 $d{p}_i$ 表示上一次选了 s 的第 i 位作为开头的扩展串

预处理一下以 i，j 开头的串冲突在哪一位

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef const int& cint;

const int mod = 1e9+7;
const int inf_int = 0x7fffffff;
const ll inf_ll = 0x7fffffffffffffff;
const double ept = 1e-9;

int t, n;
char s[5050];
ll dp[5050];
int pre[5050][5050];

void debug() {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++)
            cout << pre[i][j] << ' ';
        cout << endl;
    }
}

int main() {
    cin >> t;
    while(t--) {
        cin >> n;
        cin >> s;
        ll ans = 0;
        for(int i=1; i<n; i++) {
            int r = 1;
            for(int j=1; j+i<=n; j++) {
                if(s[j-1] != s[i+j-1]) {
                    while(r <= j) {
                        pre[r][r+i] = j;
                        ++r;
                    }
                }
            }
        }
        // debug();
        for(int i=1; i<=n; i++) {
            dp[i] = 0;
            for(int j=i-1; j >= 0; j--) {
                if(j == 0 || s[i-1] > s[j-1]) dp[i] = max(dp[i], dp[j]+n-i+1);
                else if(s[i-1] == s[j-1]) {
                    int r = pre[j][i];
                    if(r && s[r-1] < s[r-1+i-j]) dp[i] = max(dp[i], dp[j]+n-(r+i-j)+1);
                }
            }
            ans = max(ans, dp[i]);
            // cout << i << ' ' << dp[i] << endl;
        }
        cout << ans << endl;
    }
    return 0;
}