ลบกล่องใน C ++

สมมติว่าเรามีกล่องหลายกล่องที่มีสีต่างกัน สีเหล่านี้แทนด้วยจำนวนบวกต่างกัน เราสามารถสัมผัสได้หลายรอบในการแกะกล่องจนไม่มีกล่องเหลือ ในแต่ละรอบ เราสามารถเลือกกล่องต่อเนื่องที่มีสีเดียวกันได้ (ประกอบด้วย k กล่อง k>=1) แล้วเอาออกและรับ k*k คะแนน ดังนั้นหากอินพุตเป็น − [1,3,2,2,2,4,4,3,1] ผลลัพธ์จะเป็น 21

ค้นหาคะแนนสูงสุดที่คุณจะได้รับ

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

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้กล่องอาร์เรย์ i, j, k, dp อาร์เรย์ 3 มิติหนึ่งชุด
• ถ้า i> j แล้ว −
  • คืน 0
• ถ้า dp[i, j, k] ไม่เท่ากับ -1 แล้ว −
  • ส่งคืน dp[i, j, k]
• ret :=-inf
• สำหรับการตรวจสอบเงื่อนไข i + 1 <=j และ boxes[i + 1] เหมือนกับ box[i], อัปเดต (เพิ่ม i ขึ้น 1), (เพิ่ม k ขึ้น 1), ไม่ทำอะไรเลย -
• ret :=สูงสุดของ ret และ (k + 1) * (k + 1) + เรียกฟังก์ชัน Solve(boxes, i + 1, j, 0, dp)
• สำหรับการเริ่มต้น x :=i + 1 เมื่อ x <=j อัปเดต (เพิ่ม x ขึ้น 1) ทำ −
  • ถ้า box[x] เหมือนกับ box[i] แล้ว −
    • ret :=สูงสุดของ ret และแก้ปัญหา ((กล่อง, i + 1, x - 1, 0, dp) + แก้ (กล่อง, x, j, k + 1, dp))
• ส่งคืน dp[i, j, k] =ret
• จากวิธีหลัก ให้ทำดังนี้
• n :=ขนาดของกล่อง
• กำหนดอาร์เรย์ 3 มิติ dp ของคำสั่ง (n + 1) x (n + 1) x (n + 1) หนึ่งชุด เติมด้วย -1
• ส่งคืนการแก้(กล่อง 0, n - 1, 0, dp)

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

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

21