dp problem Codeforces Round #367

Revision en1, by salt_n_ice, 2020-10-10 09:59:58

here is the problem. At first, I couldn't solve it on my own so I took help from the editorial and this is what I came up with:

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
using ll=long long;
int main()
{
    ll n;
    cin>>n;
    vector<ll> c;
    for(ll i=0; i<n; ++i)
    {
        ll x;
        cin>>x;
        c.push_back(x);
    }
    vector<string> vec;
    for(ll i=0; i<n; ++i)
    {
        string f;
        cin>>f;
        vec.push_back(f);
    }
    ll dp[n][2];
    for(ll i=0; i<=n; ++i)
    {
        for(ll j=0; j<2; ++j)
        {
            dp[i][j] = numeric_limits<ll>::max()/2;
        }
    }
    dp[0][0]=0;
    dp[0][1]=c[0];
    ll n1 = 0, n2 = 0;
    for(ll i=1; i<n; ++i)
    {
        n1 = 0;
        n2 = 0;
        if(vec[i]>=vec[i-1])
            dp[i][0]=min(dp[i][0],dp[i-1][0]);
        else n1++;
        reverse(vec[i-1].begin(), vec[i-1].end());
        if(vec[i]>=vec[i-1])
            dp[i][0]=min(dp[i][0], dp[i-1][1]);
        else n1++;
        reverse(vec[i-1].begin(), vec[i-1].end());
        reverse(vec[i].begin(), vec[i].end());
        if(vec[i]>=vec[i-1])
            dp[i][1]=min(dp[i][1],dp[i-1][0]+c[i]);
        else n2++;
        reverse(vec[i-1].begin(), vec[i-1].end());
        if(vec[i]>vec[i-1])
            dp[i][1]=min(dp[i][1], dp[i-1][1]+c[i]);
        else n2++;
        reverse(vec[i-1].begin(), vec[i-1].end());
        reverse(vec[i].begin(), vec[i].end());
        if(n1==2 && n2==2)
            break;

    }
    if(n1==2 && n2==2)
        cout<<-1;
    else cout<<min(dp[n-1][0], dp[n-1][1]);
}

but it's giving me wrong answer.Can anyone help with whats wrong?

Tags #2d-dp, #debug, #dynamic programing, #string

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English salt_n_ice 2020-10-10 09:59:58 1853 Initial revision (published)