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

Автор Legendary_45, история, 17 часов назад, По-английски

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(); }

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

»
17 часов назад, # |
  Проголосовать: нравится +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();
}
  • »
    »
    16 часов назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thanks alot sir!