题目链接：https://codeforces.com/problemset/problem/706/C
题意：
给出 $n$ 个字符串，对于第 $i$ 个字符串，你可以选择花费 $c_i$ 来将它整个翻转。
要你尽量用最少的花费，使得 $n$ 个字符串按照字典序升序排序。
题解：
$f[i][0,1]$ 表示前 $i$ 个字符串，第 $i$ 个不翻转（或者翻转）的情况下，最少的花费。
AC代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF=0x3f3f3f3f3f3f3f3f; const int maxn=1e5+5; int n; string s[maxn][2]; ll c[maxn],f[maxn][2]; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>c[i]; for(int i=1;i<=n;i++) { cin>>s[i][0]; s[i][1]=s[i][0]; reverse(s[i][1].begin(),s[i][1].end()); } memset(f,INF,sizeof(f)); f[1][0]=0, f[1][1]=c[1]; for(int i=2;i<=n;i++) { if(s[i][0]>=s[i-1][0]) f[i][0]=min(f[i][0],f[i-1][0]); if(s[i][0]>=s[i-1][1]) f[i][0]=min(f[i][0],f[i-1][1]); if(s[i][1]>=s[i-1][0]) f[i][1]=min(f[i][1],f[i-1][0]+c[i]); if(s[i][1]>=s[i-1][1]) f[i][1]=min(f[i][1],f[i-1][1]+c[i]); if(f[i][0]>=INF && f[i][1]>=INF) break; } ll ans=min(f[n][0],f[n][1]); cout<<((ans>=INF)?-1:ans)<<endl; }
Codeforces 706C - Hard problem - [DP]
原文：https://www.cnblogs.com/dilthey/p/10534115.html