C++でゲームVをジャンプする

arrと呼ばれる整数の配列と整数dがあるとします。 1つのステップで、インデックスiから-

• i + xここで、i +x

• i --xここで、i --x>=0およびxは1からdの範囲です。

ここで、nは配列のサイズです。さらに、iとjの間のすべてのインデックスkについて、arr [i]>arr[j]およびarr[i]>arr [k]の場合にのみ、インデックスiからインデックスjにジャンプできます。配列の任意のインデックスを選択して、ジャンプを開始できます。訪問でき​​るインデックスの最大数を見つける必要があります。

したがって、入力がd =2のようで、高さが次のようになっている場合

次に、出力は4になります。インデックス10から開始できます。図のように、インデックス10-> 8->6->7からジャンプできます。したがって、インデックス6から開始すると、インデックス7にしかジャンプできません。13> 9であるため、インデックス5にジャンプできません。また、インデックス5はインデックス4と6の間にあり、13> 9であるため、インデックス4にジャンプできません。インデックス3からインデックス2またはインデックス1にジャンプすることはできません。

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

• 配列dpを定義する

• 関数solve（）を定義します。これには、配列arr、idx、d、

  が必要です。

• dp [idx]が-1に等しくない場合、-

  • dp [idx]

    を返します

• ret：=1

• n：=arrのサイズ

• 初期化i：=idx + 1の場合、i

  • i> idx + dの場合、-

    • ループから出てきます

  • arr [i]> =arr [idx]の場合、-

    • ループから出てきます

  • ret：=retと1の最大値+solve（arr、i、d）

• 初期化i：=idx -1の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • i

    • ループから出てきます

  • arr [i]> =arr [idx]の場合、-

    • ループから出てきます

  • ret：=retと1の最大値+solve（arr、i、d）

• dp [idx]：=ret

• retを返す

• メインの方法から、次のようにします-

• n：=arrのサイズ

• dp：=サイズnの配列を定義し、これに-1を入力します

• ret：=1

• 初期化i：=0の場合、i

  • ret：=retとsolve（arr、i、d）の最大値

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<int> dp;
   int solve(vector <int>& arr, int idx, int d){
      if (dp[idx] != -1)
      return dp[idx];
      int ret = 1;
      int n = arr.size();
      for (int i = idx + 1; i < n; i++) {
         if (i > idx + d)
         break;
         if (arr[i] >= arr[idx])
         break;
         ret = max(ret, 1 + solve(arr, i, d));
      }
      for (int i = idx - 1; i >= 0; i--) {
         if (i < idx - d)
         break;
         if (arr[i] >= arr[idx])
         break;
         ret = max(ret, 1 + solve(arr, i, d));
      }
      return dp[idx] = ret;
   }
   int maxJumps(vector<int>& arr, int d) {
      int n = arr.size();
      dp = vector<int>(n, -1);
      int ret = 1;
      for (int i = 0; i < n; i++) {
         ret = max(ret, solve(arr, i, d));
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {6,4,14,6,8,13,9,7,10,6,12};
   cout << (ob.maxJumps(v, 2));
}

入力

{6,4,14,6,8,13,9,7,10,6,12}, 2

出力

4