我是真的会自闭, 当时一直WA, 之后发现没用 long long, 修改的时候有个特别大的n == 4万多的数据 op 一直是0, 就一直卡着,晚上提交了一下就AC 了,我是真的会自闭, ACWing魔咒:做不出来,不知道哪里错了但就是错的
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include <climits>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int>costs(n);
for(int i = 0; i < n; i ++)
cin >> costs[i];
vector<string>s(n);
for(int i = 0; i < n; i ++)
cin >> s[i];
long long ans = 0;
vector<vector<long long>> dp(n, vector<long long>(2, LLONG_MAX));
dp[0][0] = (long long)0;
dp[0][1] = (long long)costs[0];
for(int i = 1; i < n; i ++)
{
if(s[i] >= s[i - 1])
{ dp[i][0] = min(dp[i][0], dp[i - 1][0]);
}
// 反转前面的
string s1 = s[i - 1];
reverse(s1.begin(), s1.end());
if(s1 <= s[i])
dp[i][0] = min(dp[i][0], dp[i - 1][1]);
// 反转后面的
string ss = s[i];
reverse(ss.begin(), ss.end());
if(s[i - 1] <= ss)
{
if(dp[i - 1][0] != LLONG_MAX)
dp[i][1] = min(dp[i][1], (long long)dp[i - 1][0] + costs[i]);
}
// 前后都反转
if(s1 <= ss)
{
if(dp[i - 1][1] != LLONG_MAX)
dp[i][1] = min(dp[i][1], (long long)dp[i - 1][1] + costs[i]);
}
// cout << i << " " << dp[i][0] << " " << dp[i][1] << endl;
}
ans = min(dp[n - 1][0], dp[n - 1][1]);
if(ans == LLONG_MAX)ans = -1;
cout << ans << endl;
return 0;
}