Last Stone Weight II ใน C++

สมมติว่าเรามีกลุ่มหิน ตอนนี้แต่ละก้อนมีน้ำหนักเป็นจำนวนเต็มบวก ในแต่ละเทิร์น เราเลือกหินสองก้อนแล้วทุบให้เข้ากัน หากก้อนหินมีน้ำหนัก x และ y โดยมี x <=y ผลของการทุบครั้งนี้จะเป็น −

• ถ้า x =y หินทั้งสองจะถูกทำลายโดยสิ้นเชิง

• ถ้า x !=y หินน้ำหนัก x จะถูกทำลายโดยสิ้นเชิง และหินน้ำหนัก y จะมีน้ำหนักใหม่ y-x

สุดท้ายเหลือหินอีกไม่เกิน 1 ก้อน เราต้องหาน้ำหนักที่น้อยที่สุดของหินก้อนนี้ (น้ำหนักจะเป็น 0 ถ้าไม่มีหินเหลือ)

ตัวอย่างเช่น หากอินพุตเป็น [2,7,4,1,8,1] ผลลัพธ์จะเป็น 1 เนื่องจากหากเราทุบ (2,4) อาร์เรย์ใหม่จะเป็น [2,4,4) ,7,1,8,1] พวกเขาทุบ (7,8) อาร์เรย์ใหม่จะเป็น [2,1,1,1] จากนั้นทุบ (2,1) อาร์เรย์จะเป็น [1,1, 1] หลังจากทุบ (1,1) แล้วจะมีเพียง 1 ครั้งเท่านั้น

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

• n :=ขนาดของอาร์เรย์หิน ตั้งค่าทั้งหมด :=0

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • รวม :=รวม + หิน[i]

• req :=ทั้งหมด / 2

• สร้างอาร์เรย์ขนาด dp req + 1 และเติมค่านี้ด้วยค่าเท็จ

• dp[0] :=true, เข้าถึง :=0

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • สำหรับ j :=req เมื่อ j – stones[i]>=0, ลด j ลง 1

    • dp[j] :=false เมื่อ (dp[j] และ dp[j – stones[i]]) ทั้งคู่เป็นเท็จ มิฉะนั้น จะเป็นจริง

    • ถ้า dp[j] เป็นจริง ให้เข้าถึง :=สูงสุดของการเข้าถึงและ j

• ผลตอบแทนรวม – (2 * ถึง)

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int lastStoneWeightII(vector<int>& stones) {
      int n = stones.size();
      int total = 0;
      for(int i = 0; i < n; i++){
         total += stones[i];
      }
      int req = total / 2;
      vector <bool> dp(req + 1, false);
      dp[0] = true;
      int reach = 0;
      for(int i = 0; i < n; i++){
         for(int j = req; j - stones[i] >= 0; j--){
            dp[j] = dp[j] || dp[j - stones[i]];
            if(dp[j]) reach = max(reach, j);
         }
      }
      return total - (2 * reach);
   }
};
main(){
   vector<int> v = {2,7,4,1,8,1};
   Solution ob;
   cout << (ob.lastStoneWeightII(v));
}

อินพุต

[2,7,4,1,8,1]

ผลลัพธ์

1