Codeforces Round #367 (Div. 2)Hard problemDP

http://codeforces.com/contest/706/problem/C 题意：给出n个字符串，可以反转其中若干个，反转第i个的话费是c【i】，问：想最后使这n个字符串字典序为从小到大有序，最小花费是多少。 对于dp，我认为深入分析后更容易知道为什么会想到这样的状态方程。以后也就可能自己想到。 分析： 只能进行反转操作，那么每个字符串的位置是固定的，那么这个问题具有相对的无后效性和最优子结构，适合用dp。 这里说是相对，是因为前面的决策对后面还是有一点影响的，具体说是第i个决策会影响到i+1个决策。 例如：为了使前i个有序时费用最小，我们没有反转第i个，但是这却可能导致第i+1个无论反转还是不反转，都无法比第i个大，但是假如反转第i个的话前i个费用提高了，但却使第i+1个可以比第i个小了。 那么我们可以采用双路dp，dp[i][0]表示第i个不反转的话最小费用，dp[i][1]表示第i个反转的话最小费用；我们先都初始化为inf表示第i个无法反转(即反转它后不能满足字典序)。 这样的双路dp的实质是对每个状态多记录了一条信息：即这个状态下是否可翻转也可不反转。不可反转我们用inf表示，可反转时它的值表示反转后最小费用。

当前出现的局面有解的只有四种：当前字符串大于前一个，或大于前一个的反串；当前的串的反串大于前一个，或大于前一个的反串。四个if语句来转移即可。

代码：（代码参考过别人的，但分析都是自己写的）

#include<bits/stdc++.h> #define inf 1e18 using namespace std; long long  num[100010]; long long dp[100010][2]; string s1[100010],s2[100010]; int main() {     int n;cin>>n;     for(int i=1;i<=n;++i)cin>>num[i];     for(int i=1;i<=n;++i){         cin>>s1[i];s2[i]=s1[i];         reverse(s2[i].begin(),s2[i].end());     }     dp[1][1]=num[1];     for(int i=2;i<=n;++i){         dp[i][1]=dp[i][0]=inf;         if(s1[i]>=s1[i-1]){             dp[i][0]=min(dp[i][0],dp[i-1][0]);         }         if(s1[i]>=s2[i-1]){             dp[i][0]=min(dp[i][0],dp[i-1][1]);         }         if(s2[i]>=s1[i-1]){             dp[i][1]=min(dp[i][1],dp[i-1][0]+num[i]);         }         if(s2[i]>=s2[i-1]){             dp[i][1]=min(dp[i][1],dp[i-1][1]+num[i]);         }     }     long long ans;     ans=min(dp[n][0],dp[n][1]);     if(ans==inf){         cout<<-1<<endl;     }     else {       cout<<ans<<endl;     }     return 0; }