题解 | dd爱科学1.0

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

int main() {
    int n; cin >> n;
    string s; cin >> s;
    s = ' ' + s;
    vector<int> dp(30);
    for(int i = 1;i <= n; i++){
        dp[s[i]-'A'] ++;
        for(int j = 0;j < 26; j++){
            if(j == s[i] - 'A') continue;
            if(s[i] >= 'A' + j){
                dp[s[i]-'A'] = max(dp[s[i]-'A'], dp[j] + 1);
            }
        }
    }
    cout << n - *max_element(dp.begin(), dp.end()) << "\n";
}
// 64 位输出请用 printf("%lld")

遍历到第i位时，将s[i]与前面的字符比较，只有当s[i]>=ch(前面字符)时，非降序序列长度才能增加,当前位s[i]对应dp[s[i]-'A'] = max(dp[ch-'A'] + 1, dp[s[i]-'A'])