题目链接： Hard problem
题意：每个字符串可以选择反转或者不反转，给出反转每个字符串的代价，问使最少的代价使得这个字符串序列成字典序。
dp[i][j] = x ： 第一维是第i个字符串，第二维表示当前字符串是否反转。x表示当前状态下使前i个字符串成字典序的最小代价。
感觉可以做的dp，然后我没写出来。T_T
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#define maxn 100100
#include <algorithm>
#define inf 1e20
#define LL long long
using namespace std; LL dp[maxn][2];
LL a[maxn]; string s[maxn];
string ss[maxn]; int main() {
//freopen("in.cpp", "r", stdin);
int n;
while(~scanf("%d", &n)) {
for (int i=1; i<=n; ++i) {
scanf("%I64d", &a[i]);
}
for (int i=1; i<=n; ++i) {
cin >> s[i];
ss[i] = s[i];
reverse(ss[i].begin(), ss[i].end());
} dp[1][0] = 0;
dp[1][1] = a[1]; for (int i=2; i<=n; ++i) {
dp[i][0] = inf;
dp[i][1] = inf;
if (s[i] >= s[i-1]) dp[i][0] = min(dp[i][0], dp[i-1][0]);
if (s[i] >= ss[i-1]) dp[i][0] = min(dp[i][0], dp[i-1][1]);
if (ss[i] >= ss[i-1]) dp[i][1] = min(dp[i][1], dp[i-1][1] + a[i]);
if (ss[i] >= s[i-1]) dp[i][1] = min(dp[i][1], dp[i-1][0] + a[i]);
}
LL ans = min(dp[n][0], dp[n][1]);
if (ans >= inf) ans = -1;
printf("%I64d\n", ans);
}
return 0;
}