题解 | #dd爱科学1.0#

思路一：

• 在保证最长上升子序列的前提下修改数最少：等价于求最长上升子序列长度

#include <bits/stdc++.h>

const int N = 1000009;

int n;
string s;
int qu[N], tot;

int finding(int x) {  /// 二分加速
    int l = 1, r = tot;
    while(l < r) {
        int mid = l + r >> 1;
        if(qu[mid] > x) r = mid;
        else l = mid + 1;
    }
    return l;
}
int main() {
    cin >> n >> s;
    for(int i = 0; i < n; i ++) {
        int x = s[i];
        if(tot == 0 || qu[tot] <= x)
            qu[++ tot] = x;
        else qu[finding(x)] = x;
    }
    cout << n - tot;
    return 0;
}

思路二：

• dp 分别记录每一位在每一个位置下所能取得的最大值，类似这题：dd爱科学2.0