0%

CodeForces 706C

CodeForces 706C - Hard problem

Hard problem

題意:

輸入N(有多少字)、每個字顛倒的成本和每個字,問你不改變這串字的先後順序,藉由顛倒某些字來將這些字排成字典順序最少需要多少成本?

思路:

直接將所有字及所有顛倒後的字存起來,然後紀錄後面的字要滿足比前面的字大的最小成本,逐個更新就是答案。

程式碼:

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
const int AMAX = 1e5 + 7;
int N, cost[AMAX];
long long dp[AMAX][2];
string s[AMAX][2];
int main()
{
cin >> N;
for(int i = 1; i <= N; ++i)
{
cin >> cost[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());
for(int j = 0; j < 2; ++j)
{
dp[i][j]= 1e18;
for(int k = 0; k < 2; ++k)
{
if(s[i][j] >= s[i - 1][k])
{
dp[i][j] = min(dp[i][j], dp[i - 1][k] + j * cost[i]);
}
}
}
}
long long ans = min(dp[N][0], dp[N][1]);
cout << (ans == 1e18 ? -1 : ans) << endl;
return 0;
}