题目链接：

　　

题目大意：

　　n(2 ≤ n ≤ 100 000)个字符串(长度不超过100000)，翻转费用为C_i(<=10⁹)，求所有字符串从上到下符合字典序从小到大的最小费用。无解输出-1。

题目思路：

　　【动态规划】

　　每个字符串有2种状态，翻转或者不翻转，每次只与上一个字符串是否翻转有关，可以用DP。

　　费用很大，要用long long。

　　无解的时候我直接break了WA了好久。

1 // 2 //by coolxxx 3 // 4 #include
      
        5 #include
       
         6 #include
        
          7 #include
         
           8 #include
          
            9 #include
           
            10 #include
            
             11 #include
             
              12 #include
              
               13 //#include
               
                14 #include
                
                 15 #define min(a,b) ((a)<(b)?(a):(b))16 #define max(a,b) ((a)>(b)?(a):(b))17 #define abs(a) ((a)>0?(a):(-(a)))18 #define lowbit(a) (a&(-a))19 #define sqr(a) ((a)*(a))20 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))21 #define mem(a,b) memset(a,b,sizeof(a))22 #define eps (1e-8)23 #define J 1000000024 #define MAX 0x7f7f7f7f25 #define PI 3.141592653589726 #define N 10000427 using namespace std;28 typedef long long LL;29 int cas,cass;30 int n,m,lll,ans;31 LL c[N];32 LL f[N][2];33 int l[2];34 char s[4][N];35 int main()36 {37 #ifndef ONLINE_JUDGE38 // freopen("1.txt","r",stdin);39 // freopen("2.txt","w",stdout);40 #endif41 int i,j,k;42 // for(scanf("%d",&cas);cas;cas--)43 // for(scanf("%d",&cas),cass=1;cass<=cas;cass++)44 // while(~scanf("%s",s))45 while(~scanf("%d",&n))46 {47 mem(f,0x7f);mark=0;48 for(i=1;i<=n;i++)49 scanf("%I64d",&c[i]);50 scanf("%s",s[0]);51 l[0]=strlen(s[0]);52 for(i=0;i
                 
                  =0)60 f[i][0]=min(f[i-1][0],f[i][0]);61 if(strcmp(s[j],s[(j^1)+2])>=0)62 f[i][0]=min(f[i-1][1],f[i][0]);63 if(strcmp(s[j+2],s[j^1])>=0)64 f[i][1]=min(f[i-1][0]+c[i],f[i][1]);65 if(strcmp(s[j+2],s[(j^1)+2])>=0)66 f[i][1]=min(f[i-1][1]+c[i],f[i][1]);67 }68 if(f[n][0]==f[0][0] && f[n][1]==f[0][0])puts("-1");69 else printf("%I64d\n",min(f[n][0],f[n][1]));70 }71 return 0;72 }73 /*74 //75 76 //77 */