cf706C(dp)

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

题意：给出n个字符串，反转第 i 个字符串需要花费 ai，问通过反转操作将n个字符串变成升序排列，最小花费是多少，不能使其升序排列的话输出-1;

思路：dp

不难想到只有当前字符串的前一个字符串会对当前字符串产生直接影响，而每个字符串都只有反转和不反转两种状态；

我们可以用dp[i][0]表示第i个字符串不反转的情况从第0到第i个字符变成升序的需要的最小花费，dp[i][1]表示第i个字符串反转的情况从第0到第i个字符变成升序的需要的最小花费；

对于第 i 个字符串我们可以选择反转或者不反转，对于每种选择又会产生三中可能, 我们用str1, str2存储当前字符串和其反转字符串，s, rs存储前一个字符串和对应反转字符串，

那么有：

当前字符串不反转:

　　str1>=s&&str1>=rs

　　str1>=s&&str1<rs

　　str1>=rs&&str1<s

当前字符串反转:

　　str2>=s&&str2>=rs

　　str2>=s&&str2<rs

　　 str2>=rs&&str2<s

想清楚了这些状态也就不难写出状态转移方程式了：

 1 　　　　　　　if(str1>=s&&str1>=rs){ 
 2                 dp[i][0]=min(dp[i-1][0], dp[i-1][1]);
 3             }else if(str1>=s){
 4                 dp[i][0]=dp[i-1][0];
 5             }else if(str1>=rs){
 6                 dp[i][0]=dp[i-1][1];
 7             }else{
 8                 ok1=false; //不反转比s, rs都要小
 9             }
10             //若当前字符串反转
11             if(str2>=s&&str2>=rs){
12                 dp[i][1]=min(dp[i-1][0], dp[i-1][1])+a[i];
13             }else if(str2>=s){
14                 dp[i][1]=dp[i-1][0]+a[i];
15             }else if(str2>=rs){
16                 dp[i][1]=dp[i-1][1]+a[i];
17             }else{
18                 ok2=false;//反转比s, rs都要小
19             }

代码：

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 
 5 const int MAXN=1e5+10;
 6 const ll inf=0x3f3f3f3f3f3f3f3f;
 7 ll dp[MAXN][2], a[MAXN];//a数组存储花费
 8 //dp[i][0]表示第i个字符串不反转的情况从第0到第i个字符变成升序的需要的最小花费,dp[i][1]表示第i个字符串反转的情况从第0到第i个字符变成升序的需要的最小花费
 9 
10 int main(void){
11     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
12     int n;
13     cin >> n;
14     for(int i=0; i<n; i++){
15         cin >> a[i];
16     }
17     bool flag=true;
18     string s, rs, str1, str2;
19     cin >> s;
20     rs=s;
21     reverse(rs.begin(), rs.end());
22     dp[0][1]+=a[0];
23     for(int i=1; i<n; i++){
24         cin >> str1;
25         str2=str1;
26         reverse(str2.begin(), str2.end());
27         if(flag){
28             bool ok1=true, ok2=true;
29             //**若当前字符串不反转
30             if(str1>=s&&str1>=rs){ 
31                 dp[i][0]=min(dp[i-1][0], dp[i-1][1]);
32             }else if(str1>=s){
33                 dp[i][0]=dp[i-1][0];
34             }else if(str1>=rs){
35                 dp[i][0]=dp[i-1][1];
36             }else{
37                 ok1=false; //不反转比s, rs都要小
38             }
39             //若当前字符串反转
40             if(str2>=s&&str2>=rs){
41                 dp[i][1]=min(dp[i-1][0], dp[i-1][1])+a[i];
42             }else if(str2>=s){
43                 dp[i][1]=dp[i-1][0]+a[i];
44             }else if(str2>=rs){
45                 dp[i][1]=dp[i-1][1]+a[i];
46             }else{
47                 ok2=false;//反转比s, rs都要小
48             }
49             if(!ok1&&!ok2){
50                 flag=false;
51             }else if(!ok1&&ok2){
52                 dp[i][0]=inf;
53             }else if(ok1&&!ok2){
54                 dp[i][1]=inf;
55             }
56         }
57         s=str1;
58         rs=str2;
59     }
60     ll ans=min(dp[n-1][0], dp[n-1][1]);
61     if(!flag||ans>=inf){
62         cout << -1 << endl;
63     }else{
64         cout << ans << endl;
65     }
66     return 0;
67 }

View Code