Codeforces Round #367 (Div. 2) C. Hard problem （DP）

本文主要是介绍Codeforces Round #367 (Div. 2) C. Hard problem （DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://codeforces.com/contest/706/problem/C

题意：n个字符串，只能进行将字符串反转的操作，反转每个字符串花费ci。问是否能让所有字符串按字典序升序排列，能则输出最小花费，不能输出-1。

和递增子序列差不多啊。

#include <iostream> 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf = 1e15;
int c[100100];
//原字符串和逆字符串 
string s[100100], rs[100100];
//dp1表示第i个字符串不反转的最小花费
//dp2表示第i个字符串反转的最小花费
ll dp1[100100], dp2[100100];  //注意会爆int，要开longlong 
int main() {int n;scanf("%d", &n);int i;for(i = 1; i <= n; i++) {scanf("%d", c + i);}for(i = 1; i <= n; i++) {cin >> s[i];rs[i] = s[i];reverse(rs[i].begin(), rs[i].end());}for(i = 0; i <= n; i++) {dp1[i] = dp2[i] = inf;}dp1[1] = 0, dp2[1] = c[1];for(i = 2; i <= n; i++) {if(s[i] >= s[i - 1]) dp1[i] = dp1[i - 1];if(rs[i] >= rs[i - 1]) dp2[i] = dp2[i - 1] + c[i];if(s[i] >= rs[i - 1]) dp1[i] = min(dp1[i], dp2[i - 1]);if(rs[i] >= s[i - 1]) dp2[i] = min(dp2[i], dp1[i - 1] + c[i]);if(dp1[i] == inf && dp2[i] == inf) break;}if(i == n + 1) {printf("%I64d\n", min(dp1[n], dp2[n]));}else {puts("-1");}return 0;
}

这篇关于Codeforces Round #367 (Div. 2) C. Hard problem （DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---