মান করুন একটি অ্যারে A (ইন্ডেক্স ১ থেকে শুরু) আছে N সংখ্যার সাথে: A1, A2, ..., AN এবং আরেকটি পূর্ণসংখ্যা B। B নির্দেশ করে যে অ্যারে A-র যেকোনো ইন্ডেক্স i থেকে আমরা i+1, i+2, ..., i+B ইন্ডেক্সে যেতে পারি যদি সেখানে যাওয়া সম্ভব হয়। এছাড়া, ইন্ডেক্স i-এ ধরা পড়লে Ai কয়েন দিতে হবে। যদি Ai -1 হয়, তবে ঐ ইন্ডেক্সে যাওয়া যাবে না।
এখন, ইন্ডেক্স ১ থেকে শুরু করে ইন্ডেক্স N-এ ন্যূনতম কয়েন খরচ করে পৌঁছাতে হবে। আমাদের ১ থেকে N পর্যন্ত ইন্ডেক্সের পথ রিটার্ন করতে হবে। একই খরচের একাধিক পথ থাকলে লেক্সিকোগ্রাফিক্যালি সবচেয়ে ছোট পথ বেছে নিতে হবে। কোনো পথ না থাকলে খালি অ্যারে রিটার্ন করবে।
ইনপুট [1,2,4,-1,2], 2 হলে আউটপুট [1,3,5]।
সমাধানের ধাপসমূহ
- n := A-র আকার
- ret অ্যারে সংজ্ঞায়িত করুন
- cost অ্যারে (আকার n) ইনফিনিট দিয়ে ভরুন
- next অ্যারে (আকার n) -1 দিয়ে ভরুন
- যদি n শূন্য হয় বা A[n-1] == -1 হয়, তবে endPoint := n-1
- cost[n-1] = A[n-1]
- i := n-2 থেকে ০ পর্যন্ত লুপ:
- যদি A[i] == -1 হয়, তবে স্কিপ করুন
- j := i+1 থেকে min(n-1, i+B) পর্যন্ত লুপ:
- যদি cost[j] + A[i] < cost[i] হয়, তবে cost[i] := cost[j] + A[i], next[i] := j, endPoint := i
- যদি endPoint != 0 হয়, তবে খালি অ্যারে রিটার্ন করুন
- endPoint != -1 পর্যন্ত লুপে ret-এ endPoint+1 যোগ করুন
- ret রিটার্ন করুন
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; 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;
}
};
int 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, ]
