题目链接：http://codeforces.com/problemset/problem/706/C
给你n个字符串，可以反转任意一个字符串，反转每个字符串都有其对应的花费ci。
经过操作后是否能满足字符串str[i]>=str[i-1]，能就输出最小花费，不能输出-1。
dp[i][0] 表示不反转i的最小花费(str[i] >= str[i - 1] || str[i] >= reverse(str[i - 1]))
dp[i][1] 则表示反转i的最小花费...
初始dp[1][0] = 0, dp[1][1] = c[1]
要是dp[i][0/1]等于-1 就不能转移了
代码写的有点糟糕，还是太渣...
//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e5 + ;
string str[N];
LL num[N], inf = 1e15;
LL dp[N][]; int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i = ; i <= n; ++i)
cin >> num[i];
for(int i = ; i <= n; ++i)
cin >> str[i];
int ok = ;
memset(dp, -, sizeof(dp));
dp[][] = , dp[][] = num[];
for(int i = ; i <= n; ++i) {
string str1 = str[i - ]; //未反转
reverse(str[i - ].begin(), str[i - ].end());
string str2 = str[i]; //未反转
reverse(str[i].begin(), str[i].end());
if(dp[i - ][] == - && dp[i - ][] == -) {
ok = -; //不行了
break;
}
if(dp[i - ][] != -) {
if(str2 >= str1) {
dp[i][] = dp[i - ][];
}
if(str[i] >= str1) {
dp[i][] = dp[i - ][] + num[i];
}
}
if(dp[i - ][] != -) {
if(str2 >= str[i - ]) {
dp[i][] = min(dp[i - ][], dp[i][] == - ? inf : dp[i][]);
}
if(str[i] >= str[i - ]) {
dp[i][] = min(dp[i - ][] + num[i], dp[i][] == - ? inf : dp[i][]);
}
}
str[i] = str2; //赋值未反转
}
if(ok == -) {
cout << - << endl;
}
else if(dp[n][] != - && dp[n][] != -) {
cout << min(dp[n][], dp[n][]) << endl;
}
else if(dp[n][] != -) {
cout << dp[n][] << endl;
}
else if(dp[n][] != -) {
cout << dp[n][] << endl;
}
else {
cout << - << endl;
}
return ;
}