CodeForce - Hard problem(706C)

문제(링크)
문제 설명:
N개의 문자열이 주어지고, 각 문자열마다 문자열을 반전시키는 비용도 주어집니다.

문자열을 반전시키거나 반전시키지 않고, 문자열을 사전식으로 정렬해야 할 때, 반전 비용의 최소값을 구하는 문제입니다.
중간에 prefix 관련 설명은
aa
aab
위 순서대로 정렬해야 한다는 뜻입니다. 만약
z
aa
이라면 -1을 출력해야 합니다. --> compare 함수에서 자동으로 판단해 줍니다.
풀이:
원본 문자열과 반전 문자열 두 개를 준비합니다.(문자열 길이의 총 합이 100000이하이므로 가능합니다.)

dp[x][0 or 1] = x번째 문자열에서 이전 문자열을 0 = 반전x , 1 = 반전o

이전 문자열과, 현재 문자열을 반전시키거나 그대로 두면서 재귀 호출합니다.
반전시킬 경우에만 energy값을 더해줍니다.

#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long
#define pii pair<int, int>
#define MAX 1000000000000000000LL

int N;
ll energy[100001];
string str[100001][2];
ll dp[100002][2];

ll recul(int now,int order) {

 if (now == N + 1) {
  return 0;
 }

 ll& ret = dp[now][order];
 //dp 메모이제이션
 if (ret != -1) return ret;
 ret = 0;
 ll o = MAX;
 ll r = MAX;
 
 if (str[now][0].compare(str[now - 1][order]) >= 0) {
  //원본 문자열과 비교
  o = recul(now + 1, 0);
 }
   
 if (str[now][1].compare(str[now - 1][order]) >= 0) {
  //반전해서 비교 - energy값이 필요
  r = recul(now + 1, 1) + energy[now];
 }

 return ret = min(o, r);
 //둘 중 작은 값을 return
}

int main(void) {
 FIO;

 cin >> N;

 for (int i = 1; i <= N; i++)
 {
  cin >> energy[i];
 }
 for (int i = 1; i <= N; i++)
 {
  cin >> str[i][0];
  str[i][1] = str[i][0];
  reverse(str[i][1].begin(), str[i][1].end());
 }
 memset(dp, -1, sizeof(dp));

 ll ans = recul(1, 0);
 
 if (ans == MAX)
  cout << "-1";
 else
  cout << ans;
}