Xóa hộp trong C ++

Giả sử chúng ta có một số hộp với các màu khác nhau Các màu này được biểu diễn bằng các số dương khác nhau. Chúng ta có thể trải qua nhiều vòng để loại bỏ các hộp cho đến khi không còn hộp nào. Trong mỗi vòng, chúng ta có thể chọn một số hộp liên tục có cùng màu (gồm k hộp, k> =1), loại bỏ chúng và nhận k * k điểm. Vì vậy, nếu đầu vào là - [1,3,2,2,2,2,4,4,3,1], thì đầu ra sẽ là 21.

Tìm số điểm tối đa bạn có thể nhận được.

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

• Xác định một hàm giải quyết (), điều này sẽ lấy một hộp mảng, i, j, k, một dp mảng 3D,
• nếu tôi> j, thì -
  • trả về 0
• nếu dp [i, j, k] không bằng -1, thì -
  • trả về dp [i, j, k]
• ret:=-inf
• để kiểm tra điều kiện i + 1 <=j và các hộp [i + 1] giống với các hộp [i], hãy cập nhật (tăng i lên 1), (tăng k lên 1), không làm gì cả -
• ret:=tối đa của ret và (k + 1) * (k + 1) + gọi hàm giải (hộp, i + 1, j, 0, dp)
• để khởi tạo x:=i + 1, khi x <=j, cập nhật (tăng x lên 1), thực hiện -
  • nếu các hộp [x] giống với các hộp [i], thì -
    • ret:=tối đa ret và giải quyết ((hộp, i + 1, x - 1, 0, dp) + giải quyết (hộp, x, j, k + 1, dp))
• return dp [i, j, k] =ret
• Từ phương pháp chính, hãy thực hiện như sau
• n:=kích thước của hộp
• Xác định một dp mảng 3D có thứ tự (n + 1) x (n + 1) x (n + 1), điền vào giá trị này bằng -1
• trả về giải quyết (ô, 0, n - 1, 0, dp)

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 solve(vector <int>& boxes, int i, int j, int k, vector < vector < vector <int > > >& dp){
      if(i > j) return 0;
      if(dp[i][j][k] != -1) return dp[i][j][k];
      int ret = INT_MIN;
      for(; i + 1 <= j && boxes[i + 1] == boxes[i]; i++, k++);
      ret = max(ret, (k + 1) * (k + 1) + solve(boxes, i + 1, j, 0, dp));
      for(int x = i + 1; x <= j; x++){
         if(boxes[x] == boxes[i]){
            ret = max(ret, solve(boxes, i + 1, x - 1, 0, dp) + solve(boxes, x, j, k + 1,          dp));
         }
      }
      return dp[i][j][k] = ret;
   }
   int removeBoxes(vector<int>& boxes) {
      int n = boxes.size();
      vector < vector < vector <int > > > dp(n + 1, vector < vector <int> > (n + 1, vector <int>(n + 1, -1)));
      return solve(boxes, 0, n - 1, 0, dp);
   }
};
main(){
   Solution ob;
   vector<int> v = {1,3,2,2,2,4,4,3,1};
   cout << (ob.removeBoxes(v));
}

Đầu vào

{1,3,2,2,2,4,4,3,1}

Đầu ra

21