मान लीजिए हमारे पास विभिन्न रंगों के कई बॉक्स हैं। ये रंग विभिन्न धनात्मक संख्याओं द्वारा दर्शाए गए हैं। हम बॉक्स को तब तक हटाने के कई दौर अनुभव कर सकते हैं जब तक कोई बॉक्स नहीं बचा। प्रत्येक दौर में हम कुछ सतत बॉक्स चुन सकते हैं जिनका रंग समान हो (k बॉक्स से बना, k >= 1), और उन्हें हटा दें और k*k अंक प्राप्त करें। तो यदि इनपुट [1,3,2,2,2,4,4,3,1] जैसा है, तो आउटपुट 21 होगा।
अधिकतम अंक ज्ञात करें जो आप प्राप्त कर सकते हैं।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -
- एक फंक्शन solve() परिभाषित करें, यह एक ऐरे boxes, i, j, k, एक 3D ऐरे dp लेगा,
- यदि i > j, तो -
- 0 वापस करें
- यदि dp[i, j, k], -1 के बराबर नहीं है, तो -
- dp[i, j, k] वापस करें
- ret := -inf
- शर्त i + 1 <= j और boxes[i + 1], boxes[i] के समान है की जांच के लिए, i बढ़ाते हुए, k बढ़ाते हुए, कुछ न करें -
- ret := ret का अधिकतम और (k + 1) * (k + 1) + solve(boxes, i + 1, j, 0, dp) फंक्शन कॉल करें
- x := i + 1 से प्रारंभ करें, जब x <= j, x बढ़ाते हुए, करें -
- यदि boxes[x], boxes[i] के समान है, तो -
- ret := ret का अधिकतम और solve(boxes, i + 1, x - 1, 0, dp) + solve(boxes, x, j, k + 1, dp)
- यदि boxes[x], boxes[i] के समान है, तो -
- dp[i, j, k] = ret वापस करें
- मुख्य विधि से, निम्न करें
- n := boxes का आकार
- क्रम (n + 1) x (n + 1) x (n + 1) का एक 3D ऐरे dp परिभाषित करें, इसे -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
