[蓝桥杯 2023 省 A] 更小的数(Smaller Number) 题解

思路分析

将子串 $s[l..r]$ 反转后数字变小，仅取决于该子串内部第一对不相等的对称字符：

• 若 s[l] > s[r]，反转后最高变化位变小，一定合法（dp[l][r] = true）；
• 若 s[l] < s[r]，一定不合法（dp[l][r] = false）；
• 若 s[l] == s[r]，则取决于内层子串 dp[l + 1][r - 1]。 按区间长度从 $2$ 到 $n$ 递推统计所有 dp[l][r] == true 的区间个数即可。时间复杂度 $O(n^2)$。

参考代码

#include <iostream>
#include <string>
using namespace std;

bool okArr[5005][5005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if (!(cin >> s)) return 0;
    int n = (int)s.size();
    long long ans = 0;
    for (int len = 2; len <= n; ++len)
    {
        for (int l = 0; l + len - 1 < n; ++l)
        {
            int r = l + len - 1;
            if (s[l] > s[r]) okArr[l][r] = true;
            else if (s[l] < s[r]) okArr[l][r] = false;
            else okArr[l][r] = (l + 1 < r - 1) ? okArr[l + 1][r - 1] : false;
            if (okArr[l][r]) ++ans;
        }
    }
    cout << ans << "\n";
    return 0;
}