মনে করুন, বিভিন্ন রঙের কিছু বক্স আছে। রঙগুলো ভিন্ন ধনাত্মক সংখ্যা দিয়ে প্রকাশ করা হয়েছে। আমরা বেশ কয়েক রাউন্ডে বক্স সরিয়ে ফেলব যতক্ষণ না কোই বক্স থাকে। প্রতিটি রাউন্ডে আমরা একই রঙের কিছু সन्नিহিত বক্স (kটি, k>=1) বেছে নিয়ে সেগুলো সরিয়ে ফেলতে পারি এবং k*k পয়েন্ট পাব।
ইনপুট [1,3,2,2,2,4,4,3,1] হলে, আউটপুট ২১। সর্বাধিক পয়েন্ট বের করতে হবে।
সমাধানের ধাপসমূহ
- solve(boxes, i, j, k, dp) ফাংশন:
- যদি i > j হয়, ০ রিটার্ন
- যদি dp[i][j][k] != -1 হয়, সেটি রিটার্ন
- ret := -INF
- যখন i+1 <= j এবং boxes[i+1] == boxes[i], i++, k++
- ret = max(ret, (k+1)*(k+1) + solve(boxes, i+1, j, 0, dp))
- x := i+1 থেকে j পর্যন্ত:
- যদি boxes[x] == boxes[i] হয়, ret = max(ret, solve(boxes, i+1, x-1, 0, dp) + solve(boxes, x, j, k+1, dp))
- dp[i][j][k] = ret রিটার্ন
- মূল ফাংশন: n := boxes.size(), 3D dp (n+1)^3 আকারে -1 দিয়ে ভরুন, solve(boxes, 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
