当前位置: 首页 > 工具软件 > Rescue! Max > 使用案例 >

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

蓬新
2023-12-01

E. Rescue Niwen!

题意:

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

分析:

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

原因:
x x x位置元素大于前面的最长上升子序列时,那么从 x ( x + 1 ) x(x+1) x(x+1)一定> x x x这个,然后递归下去 如果后面有位置与 x x x位置元素一样,那么他后面部分位置可能会取代或者填充 S ( x ) S(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);
}
 类似资料: