解题思路

我们将使用动态规划来解决这个问题。定义 $dp[i][j]$ 为使得前 $i$ 个字符串按字典序排序，且第 $i$ 个字符串在以下状态时所需的最小能量：

• $j = 0$：第 $i$ 个字符串未反转；
• $j = 1$：第 $i$ 个字符串已反转。

状态 $dp[i][j]$ 可由 $dp[i-1][0]$ 和 $dp[i-1][1]$ 转移而来。在转移时，需要检查第 $i$ 个字符串是否字典序大于或等于第 $i-1$ 个字符串：

• 如果 $j = 1$，应检查反转后的第 $i$ 个字符串；
• 对第 $i-1$ 个字符串同理（根据 $dp[i-1][0]$ 或 $dp[i-1][1]$ 对应的状态选择原始或反转后的字符串）。

转移方程为：

• $dp[i][j] = \min(dp[i][j],\ dp[i-1][0] + j \cdot c[i])$ （当第 $i-1$ 个字符串未反转且满足字典序条件时）
• $dp[i][j] = \min(dp[i][j],\ dp[i-1][1] + j \cdot c[i])$ （当第 $i-1$ 个字符串已反转且满足字典序条件时）

最终答案为 $\min(dp[n][0], dp[n][1])$。

时间复杂度：$O(n + \text{总字符串长度})$。

C++ 代码实现

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

const ll INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> c(n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }

    vector<string> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }

    vector<string> rev(n);
    for (int i = 0; i < n; ++i) {
        rev[i] = s[i];
        reverse(rev[i].begin(), rev[i].end());
    }

    vector<vector<ll>> dp(n, vector<ll>(2, INF));
    dp[0][0] = 0;
    dp[0][1] = c[0];

    for (int i = 1; i < n; ++i) {
        // 当前不反转
        if (s[i] >= s[i - 1]) {
            dp[i][0] = min(dp[i][0], dp[i - 1][0]);
        }
        if (s[i] >= rev[i - 1]) {
            dp[i][0] = min(dp[i][0], dp[i - 1][1]);
        }
        // 当前反转
        if (rev[i] >= s[i - 1]) {
            dp[i][1] = min(dp[i][1], dp[i - 1][0] + c[i]);
        }
        if (rev[i] >= rev[i - 1]) {
            dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i]);
        }
    }

    ll ans = min(dp[n - 1][0], dp[n - 1][1]);
    if (ans >= INF) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }

    return 0;
}