C++ এ বক্সগুলো সরান

ধরুন আমাদের কাছে বিভিন্ন রঙের বেশ কয়েকটি বাক্স রয়েছে এই রঙগুলি বিভিন্ন ধনাত্মক সংখ্যা দ্বারা প্রতিনিধিত্ব করে। কোনো বাক্স অবশিষ্ট না থাকা পর্যন্ত আমরা বাক্সগুলি সরানোর জন্য বেশ কয়েকটি রাউন্ড অনুভব করতে পারি। প্রতিটি রাউন্ডে আমরা একই রঙের কিছু একটানা বাক্স বেছে নিতে পারি (k বক্সের সমন্বয়ে, k>=1), এবং সেগুলি সরিয়ে k*k পয়েন্ট পেতে পারি। সুতরাং ইনপুট যদি − [1,3,2,2,2,4,4,3,1] এর মত হয়, তাহলে আউটপুট হবে 21।

আপনি পেতে পারেন সর্বোচ্চ পয়েন্ট খুঁজুন.

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

একটি ফাংশন সল্ভ () সংজ্ঞায়িত করুন, এটি একটি অ্যারে বক্স নেবে, i, j, k, একটি 3D অ্যারে dp,
যদি i> j হয়, তাহলে −
- রিটার্ন 0
যদি dp[i, j, k] -1 এর সমান না হয়, তাহলে −
- রিটার্ন dp[i, j, k]
ret :=-inf
কন্ডিশন চেক করার জন্য i + 1 <=j এবং বক্সগুলি[i + 1] বক্সের মতই হয়[i], আপডেট করুন (i 1 দ্বারা বাড়ান), (1 দ্বারা k বাড়ান), কিছুই করবেন না -
ret :=ret এর সর্বোচ্চ এবং (k + 1) * (k + 1) + ফাংশন সমাধান কল করুন (বক্স, i + 1, j, 0, dp)
আরম্ভ করার জন্য x :=i + 1, যখন x <=j, আপডেট করুন (x 1 দ্বারা বাড়ান), −
- যদি বক্সগুলি[x] বক্সের মতো হয়[i], তাহলে −
  - ret :=ret এবং solve((boxes, i + 1, x - 1, 0, dp) + solve(boxes, x, j, k + 1, dp))
রিটার্ন dp[i, j, k] =ret
মূল পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন
n :=বাক্সের আকার
একটি 3D অ্যারে ডিপি অর্ডার (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}