考虑到n的范围问题,是10^5次方,那么只能用空间时间为n或者nlogn的方法

现在面对一个单词就有两个决策，要么反转它，要么不反转。所以很轻易地就想到了二维dp。

用 dp[i][0] 表示不反转第i个单词 而且能使1~i这i个单词按照字典序排列的 最小消费

用 dp[i][0] 表示反转第i个单词 而且能使1~i这i个单词按照字典序排列的 最小消费

值得关注的是,为了方便操作,降低常数复杂度,可以先预处理反转后的字符串

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 4;
typedef long long ll;
const ll inf = 1e18;
ll dp[maxn][2];
int a[maxn];
string str[maxn], rev[maxn];
int main() {
    memset(dp, 0, sizeof(dp));
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) dp[i][0] = dp[i][1] = inf;
    dp[1][0] = 0; dp[1][1] = a[1];
    for (int i = 1; i <= n; i++) {
        cin >> str[i];
        rev[i] = str[i];
        reverse(rev[i].begin(), rev[i].end());
    }
        //dp[i][0] 表示当前位置不翻转
        //dp[i][1] 表示当前位置翻转
    for (int i = 2; i <= n; i++) {
        if (str[i - 1] <= str[i]) { 
            dp[i][0] = min(dp[i][0], dp[i - 1][0]);
        } 
        if (rev[i - 1] <= str[i]) {
            dp[i][0] = min(dp[i][0], dp[i - 1][1]);
        }
        if (str[i - 1] <= rev[i]) {
            dp[i][1] = min(dp[i][1], dp[i - 1][0] + a[i]);
        }
        if (rev[i - 1] <= rev[i]) {
            dp[i][1] = min(dp[i][1], dp[i - 1][1] + a[i]);
        }
    }
    if (min(dp[n][0], dp[n][1]) >= inf) {
        cout << "-1" << endl; return 0;
    } else {
        cout << min(dp[n][0], dp[n][1]) << endl;
    }
    return 0;
}