题解 | #dd爱科学2.0#

思路：

• dp
  • 我们枚举每一位变成每一种字符（26种）时的花费（保证此时字符串递增）。

值得注意的是当我们计算花费时需要取得当前位最小值，就必须要去遍历前面状态小于自己字符的花费取最小，这个问题可以通过加一个额外的记录最小值的变量完成，不过在代码里我们做的更绝：每一位保存的都是全体最小值，其意义为：当前位置取不大于当前字符的字符时的最小花费。这样问题就解决了。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define intmax 0x7fffffff
#define halfintmax 0x3fffffff

typedef pair<int, int> pii;
typedef pair<int, char> pic;

const int N = 1000006;
const int mod = 1e9 + 7;

int n, dp[N][30];

int main() {
    cin >> n;
    char c;
    int x;
    for(int i = 1; i <= n; i ++) dp[i][0] = 0x3fffffff;
    for(int i = 1; i <= n; i ++) {
        scanf(" %c", &c);
        x = c - 'A' + 1;
        for(int j = 1; j <= 26; j ++) {
            dp[i][j] = abs(x - j) + dp[i - 1][j];
            dp[i][j] = min(dp[i][j], dp[i][j - 1]);
        }
    }
    int ans = 0x3fffffff;
    for(int i = 1; i <= 26; i ++)
        ans = min(ans, dp[n][i]);
    cout << ans;
    return 0;
}