C++에서 상자 제거

<시간/>

색상이 다른 여러 상자가 있다고 가정합니다. 이러한 색상은 다른 양수로 표시됩니다. 상자가 하나도 남지 않을 때까지 상자를 제거하기 위해 여러 라운드를 경험할 수 있습니다. 각 라운드에서 동일한 색상(k개의 상자, k>=1으로 구성)을 가진 연속적인 상자를 선택하고 제거하고 k*k 포인트를 얻을 수 있습니다. 따라서 입력이 − [1,3,2,2,2,4,4,3,1]과 같으면 출력은 21이 됩니다.

얻을 수 있는 최대 포인트를 찾으세요.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

solve() 함수를 정의하면 배열 상자, 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만큼 증가), (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 및 solve((boxes, i + 1, x - 1, 0, dp) + solve(boxes, x, j, k + 1, dp))의 최대값
dp[i, j, k] =ret를 반환
메인 방법에서 다음을 수행합니다.
n :=상자 크기
(n + 1) x (n + 1) x (n + 1)의 3D 배열 dp 하나를 정의하고 -1로 채우세요.
return 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}