問題
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; }