➤ Problem Link : 706C. Hard problem
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ll n;
cin>>n;
ll energy[n+1];
string arr[n+1][2];
ll dp[n+1][2];
for(ll i=1;i<=n;i++)
cin>>energy[i];
for(ll i=1;i<=n;i++)
{
cin>>arr[i][0];
arr[i][1]=arr[i][0];
reverse(arr[i][1].begin(),arr[i][1].end());
}
string s;
dp[1][0]=0;
dp[1][1]=energy[1];
bool flag=0;
for(ll i=2;i<=n;i++)
{
s=arr[i][0];
dp[i][0]=pow(10,15);
dp[i][1]=pow(10,15);
if(arr[i-1][0]<s || arr[i-1][0]==s)
dp[i][0]=min(dp[i][0],dp[i-1][0]);
if(arr[i-1][1]<s || arr[i-1][1]==s)
dp[i][0]=min(dp[i][0],dp[i-1][1]);
s=arr[i][1];
if(arr[i-1][0]<s || arr[i-1][0]==s)
dp[i][1]=min(dp[i][1],energy[i]+dp[i-1][0]);
if(arr[i-1][1]<s || arr[i-1][1]==s)
dp[i][1]=min(dp[i][1],energy[i]+dp[i-1][1]);
if(dp[i][0]==pow(10,15) && dp[i][1]==pow(10,15))
{
flag=1;
break;
}
}
if(flag)
cout<<"-1";
else
cout<<min(dp[n][0],dp[n][1]);
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.