#### Codefores 706C ## ##
题目大意：给你n个字符串，要求满足字典序排序 等价于 s[i]>=s[i-1]。每个操作需要花费能量，操作只能反转。如果不能满足题意输出-1。题目分析：动态规划。dp数组有两种状态，反转与不反转，可用0/1表示。有四种情况， dp[now][0]与dp[now-1][0/1],dp[now][0/1]与dp[now-1][0] #include<bits/stdc++.h> #define me(a,b) memset(a,b,sizeof(a)) #define MAX 100005 #define INF 1e16 #define LL long long using namespace std; LL dp[MAX][2]; string s[MAX],ds[MAX]; LL cost[MAX]; int main() { int n; while(cin>>n) { for(int i=1;i<=n;i++) cin>>cost[i]; for(int i=1;i<=n;i++) { cin>>s[i]; ds[i]=s[i]; reverse(ds[i].begin(),ds[i].end()); } for(int i=1;i<=n;i++) dp[i][0]=dp[i][1]=INF; dp[1][0]=0;dp[1][1]=cost[1]; for(int i=2;i<=n;i++) { if(s[i]>=s[i-1]) dp[i][0]=dp[i-1][0]; if(ds[i]>=s[i-1]) dp[i][1]=dp[i-1][0]+cost[i]; if(s[i]>=ds[i-1]) dp[i][0]=min(dp[i-1][1],dp[i][0]); if(ds[i]>=ds[i-1]) dp[i][1]=min(dp[i-1][1]+cost[i],dp[i][1]); } printf("%I64d\n",min(dp[n][1],dp[n][0])==INF?-1:min(dp[n][1],dp[n][0])); } return 0; }注意数据范围，用了一次0x3f 果断太小 ，大家还是别偷懒 写个for吧。
