Codeforces 706 C. Hard problem (dp)

题目链接：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 就不能转移了

代码写的有点糟糕，还是太渣...

 1 //#pragma comment(linker, "/STACK:102400000, 102400000")
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cstdio>
 7 #include <string>
 8 #include <vector>
 9 #include <cmath>
10 #include <ctime>
11 #include <list>
12 #include <set>
13 #include <map>
14 using namespace std;
15 typedef long long LL;
16 typedef pair <int, int> P;
17 const int N = 1e5 + 5;
18 string str[N];
19 LL num[N], inf = 1e15;
20 LL dp[N][2];
21 
22 int main()
23 {
24     ios::sync_with_stdio(false);
25     int n;
26     cin >> n;
27     for(int i = 1; i <= n; ++i)
28         cin >> num[i];
29     for(int i = 1; i <= n; ++i)
30         cin >> str[i];
31     int ok = 0;
32     memset(dp, -1, sizeof(dp));
33     dp[1][0] = 0, dp[1][1] = num[1];
34     for(int i = 2; i <= n; ++i) {
35         string str1 = str[i - 1]; //未反转
36         reverse(str[i - 1].begin(), str[i - 1].end());
37         string str2 = str[i]; //未反转
38         reverse(str[i].begin(), str[i].end());
39         if(dp[i - 1][0] == -1 && dp[i - 1][1] == -1) {
40             ok = -1; //不行了
41             break;
42         }
43         if(dp[i - 1][0] != -1) {
44             if(str2 >= str1) {
45                 dp[i][0] = dp[i - 1][0];
46             }
47             if(str[i] >= str1) {
48                 dp[i][1] = dp[i - 1][0] + num[i];
49             }
50         }
51         if(dp[i - 1][1] != -1) {
52             if(str2 >= str[i - 1]) {
53                 dp[i][0] = min(dp[i - 1][1], dp[i][0] == -1 ? inf : dp[i][0]);
54             }
55             if(str[i] >= str[i - 1]) {
56                 dp[i][1] = min(dp[i - 1][1] + num[i], dp[i][1] == -1 ? inf : dp[i][1]);
57             }
58         }
59         str[i] = str2; //赋值未反转
60     }
61     if(ok == -1) {
62         cout << -1 << endl;
63     }
64     else if(dp[n][0] != -1 && dp[n][1] != -1) {
65         cout << min(dp[n][0], dp[n][1]) << endl;
66     }
67     else if(dp[n][0] != -1) {
68         cout << dp[n][0] << endl;
69     }
70     else if(dp[n][1] != -1) {
71         cout << dp[n][1] << endl;
72     }
73     else {
74         cout << -1 << endl;
75     }
76     return 0;
77 }

View Code