เส้นทางเหรียญใน C ++

สมมติว่าเรามีอาร์เรย์ A (ดัชนีเริ่มต้นที่ 1) โดยมีตัวเลข N:A1, A2, ... , AN และจำนวนเต็ม B อีกจำนวนหนึ่ง จำนวนเต็ม B แสดงว่าจากดัชนีใดๆ คือ i ในอาร์เรย์ A เราสามารถข้ามไปยังค่าใดก็ได้ หนึ่งในตำแหน่งในอาร์เรย์ A ที่ทำดัชนี i+1, i+2, …, i+B หากสามารถข้ามสถานที่นี้ไปได้ นอกจากนี้ หากเราเหยียบดัชนี i เราต้องจ่ายจำนวนเหรียญ Ai หาก Ai เป็น -1 แสดงว่าเราไม่สามารถข้ามไปยังตำแหน่งที่จัดทำดัชนี i ในอาร์เรย์ได้

ตอนนี้ เมื่อเราเริ่มต้นจากตำแหน่งที่จัดทำดัชนี 1 ในอาร์เรย์ A และเป้าหมายของเราคือไปถึงสถานที่ที่จัดทำดัชนี N โดยใช้เหรียญขั้นต่ำ เราต้องคืนค่าเส้นทางของดัชนี (เริ่มจาก 1 ถึง N) ในอาร์เรย์ที่เราควรนำไปใช้เพื่อไปยังตำแหน่งที่จัดทำดัชนี N โดยใช้เหรียญขั้นต่ำ ถ้าเรามีหลายเส้นทางที่มีต้นทุนเท่ากัน เราต้องหาเส้นทางดังกล่าวที่เล็กที่สุดตามพจนานุกรม และถ้าเราไม่มีเส้นทางที่เป็นไปได้ในการเข้าถึงสถานที่ที่จัดทำดัชนี N เราจะคืนค่าอาร์เรย์ที่ว่างเปล่า

ดังนั้น หากอินพุตเป็น [1,2,4,-1,2], 2 เอาต์พุตจะเป็น [1,3,5]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ A

• กำหนดอาร์เรย์ ret

• กำหนดราคาอาร์เรย์ขนาด n และเติมด้วย inf

• กำหนดอาร์เรย์ถัดจากขนาด n และเติมด้วย -1

• ถ้า n ไม่เป็นศูนย์ หรือ A[n - 1] เหมือนกับ -1 แล้ว −

  • จุดสิ้นสุด :=n - 1

• ราคา[n - 1] =A[n - 1]

• สำหรับการเริ่มต้น i :=n - 2 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -

  • ถ้า A[i] เหมือนกับ -1 แล้ว −

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • สำหรับ j ในช่วง i + 1 ถึงค่าต่ำสุดของ (n - 1) และ i + B ให้เพิ่ม j ขึ้น 1 −

    • ถ้า cost[j] + A[i]

      • ราคา[i] :=ราคา[j] + A[i]

      • ต่อไป[i] :=j

      • จุดสิ้นสุด :=ผม

• ถ้าจุดสิ้นสุดไม่เท่ากับ 0 ดังนั้น −

  • คืนค่าอาร์เรย์ว่าง

• สำหรับจุดสิ้นสุดไม่เท่ากับ -1 ให้อัปเดตจุดสิ้นสุด =ถัดไป[จุดสิ้นสุด] ทำ -

  • ใส่ endPoint + 1 ที่ส่วนท้ายของ ret

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> cheapestJump(vector<int>& A, int B) {
      int n = A.size();
      vector <int> ret;
      vector <int> cost(n, 1e9);
      vector <int> next(n, -1);
      if(!n || A[n - 1] == -1) return {};
      int endPoint = n - 1;
      cost[n - 1] = A[n - 1];
      for(int i = n - 2; i >= 0; i--){
         if(A[i] == -1) continue;
         for(int j = i + 1 ; j <= min(n - 1, i + B); j++){
            if(cost[j] + A[i] < cost[i]){
               cost[i] = cost[j] + A[i];
               next[i] = j;
               endPoint = i;
            }
         }
      }
      if(endPoint != 0) return {};
      for(;endPoint != - 1; endPoint = next[endPoint]){
         ret.push_back(endPoint + 1);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,4,-1,2};
   print_vector(ob.cheapestJump(v, 2));
}

อินพุต

{1,2,4,-1,2}, 2

ผลลัพธ์

[1, 3, 5, ]