Блог пользователя I_Like_Cute_Grils

Could u plz point out where does my recursive approach is flawed, what i am doing wrong,Plz
Автор I_Like_Cute_Grils, история, 19 месяцев назад, По-английски

https://codeforces.me/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(); }

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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();
}
→ Ответить