Legendary_45's blog

Could u plz point out where does my recursive approach is flawed, what i am doing wrong,Plz
By Legendary_45, history, 17 hours ago, In English

https://codeforces.net/problemset/problem/1659/C

include <bits/stdc++.h>

/*.......................code by LegendARY...............................*/ using namespace std; using ll = long long; // my recusive solution ll Min_dist(ll capital,ll n,ll conq,ll a,ll b,vector&arr){ if(conq >= n-1){ // last wale to direct return b*(arr[n-1]-capital); } // c1 ko don't change, // c1 ko change kr do: take out the minimum; return min(b*abs(capital-arr[conq])+Min_dist(capital,n,conq+1,a,b,arr) ,a*abs(capital-arr[conq])+b*abs(arr[conq]-arr[conq+1])+Min_dist(arr[conq],n,conq+1,a,b,arr));
} //cout<<fixed<<setprecision(6) <<vv; void MYFUN(){ ll n,a,b; cin>>n>>a>>b; vectorarr(n); for(auto &it:arr) cin>>it; ll c1 =0; cout<<Min_dist(0,n,1,a,b,arr)+b*(arr[0])<<endl; } // u had to choose these three

int main(){ ll n; cin>>n; while(n--)MYFUN(); }

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
16 hours ago, # |
  Vote: I like it +8 Vote: I do not like it

You manually added the conquer cost for the first city (index 0) and started recursion from index 1. This led to missing the current city's cost in the recursive steps and caused incorrect handling of the initial city.

Try this 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll Min_dist(ll capital, ll n, ll conq, ll a, ll b, vector<ll>& arr) {
    if (conq >= n) {
        return 0;
    }
    ll current_cost = b * abs(arr[conq] - capital);
    ll option1 = current_cost + Min_dist(capital, n, conq + 1, a, b, arr);
    ll move_cost = a * abs(arr[conq] - capital);
    ll option2 = current_cost + move_cost + Min_dist(arr[conq], n, conq + 1, a, b, arr);
    return min(option1, option2);
}

void MYFUN() {
    ll n, a, b;
    cin >> n >> a >> b;
    vector<ll> arr(n);
    for (auto &it : arr) cin >> it;
    cout << Min_dist(0, n, 0, a, b, arr) << endl;
}

int main() {
    ll t;
    cin >> t;
    while (t--) MYFUN();
}
→ Reply
  • »
    »
    16 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks alot sir!

    → Reply