Hard problem [Codeforces 367 : Div2 C]

問題

http://codeforces.com/contest/706/problem/C

n個の文字列が順に与えられる。
n個の文字列が辞書順昇順となるようにしたい。
各文字列はコストciで反転させることができる。
辞書順昇順とするための最小コストを求めよ。
辞書順昇順とできないなら"-1"を出力

なお、辞書順は等しくても良い

2 <= n <= 10^5
0 <= ci <= 10^9
文字列の文字数の総和は10^5を超えない

考察

1. 最後の条件が最も怪しい
2. 普通ならいらなくない？って感じ
3. ここから考えても全然思いつかないわ

4. 最小コストなんで2分探索とかDPとかかな？
5. DPっぽいぞ
6. 理由としては「順に選ぶこと前提である」「最後に選んだもの以外後に関係無い」「最小値を求める」

7. 以下のようにDPを作って更新

dp[i][j] = 
 j = 0 : i番目まで辞書順で最後が反転してないコスト最小値
 j = 1 : i番目まで辞書順で最後が反転してるコスト最小値
「i番目のそのまま <= i+1番目のそのまま」
dp[i+1][0] = min(dp[i+1][0], dp[i][0])
「i番目の反転 <= i+1番目のそのまま」
dp[i+1][0] = min(dp[i+1][0], dp[i][1])
「i番目のそのまま <= i+1番目の反転」
dp[i+1][1] = min(dp[i+1][1], dp[i][0])
「i番目の反転 <= i+1番目の反転」
dp[i+1][1] = min(dp[i+1][1], dp[i][1])

8. min(dp[n][0], dp[n][1])が答え
9. INFなら"-1"

実装

http://codeforces.com/contest/706/submission/19969623

#define INF 1LL<<60
typedef long long ll;
int n;
int c[101010];
string s[101010];
string rs[101010];
ll dp[101010][2];
//-----------------------------------------------------------------
int main() {
	cin >> n;
	rep(i, 0, n) scanf("%d", &c[i]);
	rep(i, 0, n) cin >> s[i];
	rep(i, 0, n) rs[i] = s[i], reverse(rs[i].begin(), rs[i].end());

	rep(i, 0, n + 1) rep(j, 0, 2) dp[i][j] = INF;
	dp[1][0] = 0;
	dp[1][1] = c[0];

	rep(i, 1, n) {
		if (s[i - 1] <= s[i]) dp[i + 1][0] = min(dp[i + 1][0], dp[i][0]);
		if (rs[i - 1] <= s[i]) dp[i + 1][0] = min(dp[i + 1][0], dp[i][1]);
		if (s[i - 1] <= rs[i]) dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + c[i]);
		if (rs[i - 1] <= rs[i]) dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + c[i]);
	}

	ll ans = min(dp[n][0], dp[n][1]);
	if (ans == INF) ans = -1;
	cout << ans << endl;
}