C++でボックスを削除する

異なる色のボックスがいくつかあるとします。これらの色は異なる正の数で表されます。ボックスがなくなるまで、ボックスを削除するために数ラウンドを経験することができます。各ラウンドで、同じ色の連続したボックス（k個のボックスで構成されます。k> =1）をいくつか選択し、それらを削除してk*kポイントを取得できます。したがって、入力が− [1,3,2,2,2,4,4,3,1]の場合、出力は21になります。

あなたが得ることができる最大のポイントを見つけてください。

これを解決するには、次の手順に従います-

• 関数solve（）を定義します。これには、配列ボックスi、j、k、1つの3D配列dpが必要です。
• i> jの場合、-
  • 0を返す
• dp [i、j、k]が-1に等しくない場合、-
  • return dp [i、j、k]
• ret：=-inf
• 条件i+1 <=jをチェックし、boxes [i +1]はboxes[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]がboxes[i]と同じ場合、-
    • ret：=retとsolve（（boxes、i + 1、x --1、0、dp）+ resolve（boxes、x、j、k + 1、dp））の最大値
• return dp [i、j、k] =ret
• メインの方法から、次の手順を実行します
• n：=ボックスのサイズ
• 次数（n + 1）x（n + 1）x（n + 1）の3D配列dpを1つ定義し、これに-1を入力します
• returnsolve（ボックス、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