Last Stone Weight II trong C ++

Giả sử chúng ta có một bộ sưu tập đá, bây giờ mỗi tảng đá có trọng lượng là một số nguyên dương. Trong mỗi lượt, chúng ta chọn hai hòn đá bất kỳ và đập chúng vào nhau. Nếu các viên đá có trọng lượng x và y với x <=y. Kết quả của cú đập này sẽ là -

• Nếu x =y, cả hai viên đá đều bị phá hủy hoàn toàn;

• Nếu x! =Y, viên đá có trọng lượng x bị phá hủy hoàn toàn và viên đá có trọng lượng y có trọng lượng mới là y-x.

Cuối cùng, chỉ còn lại nhiều nhất 1 viên đá. Chúng ta phải tìm trọng lượng nhỏ nhất có thể của viên đá này (trọng lượng bằng 0 nếu không còn viên đá nào.)

Vì vậy, ví dụ, nếu đầu vào là [2,7,4,1,8,1], thì đầu ra sẽ là 1. Điều này là bởi vì nếu chúng ta smash (2,4), thì mảng mới sẽ là [2 , 7,1,8,1], họ smash (7,8), mảng mới sẽ là [2,1,1,1], sau đó smash (2,1), mảng sẽ là [1,1, 1], sau cú đập đó (1,1), vì vậy sẽ chỉ có 1 ở đó.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng đá, đặt tổng:=0

• cho tôi trong phạm vi từ 0 đến n - 1

  • tổng số:=tổng số + đá [i]

• yêu cầu:=tổng / 2

• tạo một mảng dp có kích thước req + 1 và điền vào giá trị này bằng các giá trị sai

• dp [0]:=true, đạt:=0

• cho tôi trong phạm vi từ 0 đến n - 1

  • đối với j:=req, khi j - stone [i]> =0, giảm j đi 1

    • dp [j]:=false khi (dp [j] và dp [j - stone [i]]) đều sai, ngược lại là true

    • nếu dp [j] là true, thì reach:=max của phạm vi tiếp cận và j

• tổng lợi nhuận - (2 * phạm vi tiếp cận)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

1