পাইথনে অক্ষর পুনরাবৃত্তি এড়াতে ন্যূনতম মুছে ফেলার খরচ খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে একটি স্ট্রিং s এবং পূর্ণসংখ্যার আরেকটি অ্যারে আছে যাকে বলা হয় cost যেখানে cost[i] s-এ ith অক্ষরটি মুছে ফেলার ব্যয়কে উপস্থাপন করে। আমাদের মুছে ফেলার সর্বনিম্ন খরচ খুঁজে বের করতে হবে যাতে একে অপরের পাশে দুটি একই অক্ষর নেই। আমাদের মনে রাখতে হবে যে আমরা একই সময়ে নির্বাচিত অক্ষরগুলি মুছে ফেলব। তাই একটি অক্ষর মুছে ফেলার পরে, অন্যান্য অক্ষর মুছে ফেলার খরচ পরিবর্তন হবে না।

সুতরাং, যদি ইনপুটটি s ="pptpp", cost =[2,3,4,5,2] এর মত হয়, তাহলে আউটপুট হবে 4 কারণ যদি আমরা 2+2 =4 খরচ সহ প্রথম এবং শেষ p সরিয়ে ফেলি, তাহলে স্ট্রিংটি হবে "ptp" এখানে কোনো দুটি অভিন্ন অক্ষর একের পর এক উপস্থিত নেই

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব−

• cost_f :=0
• i :=1
• ইন্ড :=0
• এর জন্য 1 থেকে s - 1 এর আকারের মধ্যে, কর
  • cur :=s[i], c_cost :=খরচ[i]
  • আগের :=s[i-1], p_cost :=খরচ[i-1]
  • যদি ind 1 এর মত হয়, তাহলে
    • পূর্ববর্তী :=পূর্ববর্তী_i, p_cost :=cost_i
  • যদি cur আগের মত হয়, তাহলে
    • যদি c_cost>=p_cost, তাহলে
      • cost_f :=cost_f + p_cost
      • prev_i :=0, cost_i :=0
      • ইন্ড :=0
    • যদি c_cost
    • cost_f :=cost_f + c_cost
    • ইন্ড :=1
    • prev_i :=prev, cost_i :=p_cost
• অন্যথায়,
  • prev_i :=0, cost_i :=0
  • ইন্ড :=0

উদাহরণ

আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:

def solve(s, cost):
   cost_f = 0
   i = 1
   ind = 0

   for i in range(1, len(s)):
      cur, c_cost = s[i], cost[i]
      prev, p_cost = s[i-1], cost[i-1]
      if ind == 1:
         prev, p_cost = prev_i, cost_i

      if cur == prev:
         if c_cost >= p_cost:
            cost_f += p_cost
            prev_i, cost_i = 0,0
            ind = 0

         if c_cost < p_cost:
            cost_f += c_cost
            ind = 1
            prev_i, cost_i = prev, p_cost

      else:
         prev_i, cost_i = 0,0
         ind = 0
   return cost_f

s = "pptpp"
cost = [2,3,4,5,2]
print(solve(s, cost))

ইনপুট

"pptpp", [2,3,4,5,2]

আউটপুট

4