考虑到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; }
