题意：给你一些字符串，然后要把这些字符串变成字典序
分析：因为决策只会有前面的字符影响，并且具有最优子结构（自己想想）
具体实现详见代码。
#include<bits/stdc++.h> using namespace std; const long long INF = 3e18; const int maxn = 1e5 + 20; long long B[maxn] , dp[maxn][2]; vector<string > A; int main(void) { int n; cin >> n; string s; A.push_back(""); A.push_back(""); for(int i = 1; i <= n; i ++) { scanf("%I64d",B+i); } for(int i = 1; i <= n; i ++) { cin>>s; A.push_back(s); reverse(s.begin(),s.end()); A.push_back(s); } for(int i = 1 ; i <= n; i ++) for(int j = 0; j< 2;j++) dp[i][j] = INF; dp[0][0] = dp[0][1] = 0; // for(int i = 0;i<A.size();i++) cout<<A[i]<<" "<<i<<endl; for(int i = 1;i <= n;i ++) { for(int j = 0;j < 2; j ++) { for(int k = 0; k < 2; k++) { if(dp[i-1][j] != INF && A[2*(i-1) + j] <= A[2*i + k]) { dp[i][k] = min(dp[i][k] , dp[i-1][j] + k*B[i]); } } } } long long res = min(dp[n][1],dp[n][0]); if(res == INF) cout<<-1; else cout<<res; }