AcWing 5571. 反转字符串
原题链接
中等
作者:
虚实相依
,
2024-04-20 22:09:55
,
所有人可见
,
阅读 26
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int w[N];
string s[N][2];
LL f[N][2]; //对于字符串s[i]的反转状态j(0无/1有)
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> w[i];
for (int i = 0; i < n; i ++ )
{
cin >> s[i][0];
s[i][1] = s[i][0];
reverse(s[i][1].begin(), s[i][1].end());//s[i][0]是反转前字符串,s[i][1]是反转后字符串;
}
memset(f, 0x3f, sizeof f); //最大值初始化,将数组 f 中的每个字节都设置为 0x3f
f[0][0] = 0, f[0][1] = w[0];
for (int i = 1; i < n; i ++ )
for (int j = 0; j < 2; j ++ )//遍历后面字符串的状态
for (int k = 0; k < 2; k ++ )//遍历前面字符串的状态
if (s[i][j] >= s[i - 1][k]) //逐字符比较ASCII码,若后一个串的某位>=前一个串的某位,满足dp集合更新条件
f[i][j] = min(f[i][j], f[i - 1][k] + j * w[i]);//更新集合
LL res = min(f[n - 1][0], f[n - 1][1]); //最后一个串的是否翻转两种条件下取最小值
if (res == 0x3f3f3f3f3f3f3f3fll) res = -1; //long long占8字节,每个字节都取较大值,最后加上ll;
//不加ll,会被认为是int,超出int的表示范围
cout << res << endl;
return 0;
}