C dd爱科学2.0

思路

sorry，简单DP, 为什么我只想到贪心, 赏自己两巴掌.

状态表示dp[i][j] : 已经处理前i个字母，且当前末尾字符是j的最小花费
状态计算: 划分集合, 每个小集合都是决策，即前一个字母是A~Z的最优情况, 前提要保持非递减
边界：f[0][0~26] = 0

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define rep(a, b) for(int i = a; i <= b; i ++)
using namespace std;

const int N = 1000010;

int a[N];
char str[N];
int dp[N][26];

int main(){
    int n;
    cin >> n >> str + 1;

    rep(1, n){
        for(int j = 0; j < 26; j ++){
            dp[i][j] = 1e9;
            for(int k = 0; k <= j; k ++){
                dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(str[i]-'A'-j));
            }
        }
    }

    int res = 1e9;
    rep(0, 25){
        res = min(res, dp[n][i]);
    }

    cout << res << endl;

    return 0;
}