Hard problem T15 D57

[传送门]( Problem - C - Codeforces (Unofficial mirror site, accelerated for Chinese users) )

思路

dp

\(f[i][0]\)表示到这个字符串时不反转的最小代价

\(f[i][1]\)表示到这个字符串时反转的最小代价

参考代码

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define si size()
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const int qs=1e5+7;
ll a[qs],f[qs][2],n; 
string s[qs],rs[qs]; 
 
int main(){
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=n;++i) {
		cin>>s[i];
		rs[i]=s[i];
		f[i][0]=f[i][1]=1e16;
		reverse(rs[i].begin(),rs[i].end());
	}
	f[1][0]=0,f[1][1]=a[1];
	for(int i=2;i<=n;++i){
		int fg=0;
		if(s[i]>=s[i-1]&&f[i-1][0]!=1e16)   fg=1,f[i][0]=min(f[i][0],f[i-1][0]);
		if(s[i]>=rs[i-1]&&f[i-1][1]!=1e16)  fg=1,f[i][0]=min(f[i][0],f[i-1][1]);
		if(rs[i]>=s[i-1]&&f[i-1][0]!=1e16)  fg=1,f[i][1]=min(f[i][1],f[i-1][0]+a[i]);
		if(rs[i]>=rs[i-1]&&f[i-1][1]!=1e16) fg=1,f[i][1]=min(f[i][1],f[i-1][1]+a[i]);
		if(!fg){
			cout<<"-1\n"; return 0;
		}
	}
	cout<<min(f[n][0],f[n][1])<<"\n"; 
	
	return 0;
}