C++で配列を厳密に増やす

2つの配列arr1とarr2があり、これらは整数を格納できると仮定します。 arr1を厳密に増やすために必要な操作の最小数を見つける必要があります。ここでは、2つのインデックス0 <=i

caPending-3nで配列arr1を厳密に増加させない場合は、-1を返します。

したがって、入力がarr1 =[1,5,3,7,8]、arr2 =[1,3,2,5]の場合、5を2に置き換えることができるため、出力は1になります。配列は[1,2,3,7,8]になります。

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

• 関数solve（）を定義します。これは、配列arr1、配列arr2、i、j、prev、1つの2D配列dp、

  を取ります。

• i> =arr1のサイズの場合、-

  • 1を返す

• j =arr2[j]およびupper

  からのarr2のサブ配列の最初の要素

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

  • dp [i、j]

    を返します

• ret：=arr2のサイズ+1

• prev

  • ret：=retとsolve（arr1、arr2、i + 1、j、arr1 [i]、dp）の最小値

• j

  • ret：=retの最小値と1+solve（arr1、arr2、i + 1、j、arr2 [j]、dp）

• dp [i、j] =ret

  を返します

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

• 配列arr2を並べ替える

• n：=arr1のサイズ

• m：=arr2のサイズ

• サイズ2005x2005の2D配列dpを1つ定義し、これに-1を入力します

• ret：=resolve（arr1、arr2、0、0、-inf、dp）

• return（ret> arr2のサイズの場合は-1、それ以外の場合はret-1）

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& arr1, vector<int>& arr2, int i, int j, int prev, vector<vector<int> >& dp){
      if (i >= arr1.size())
         return 1;
      j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();
      if (dp[i][j] != -1)
         return dp[i][j];
      int ret = arr2.size() + 1;
      if (prev < arr1[i]) {
         ret = min(ret, solve(arr1, arr2, i + 1, j, arr1[i], dp));
      }
      if (j < arr2.size()) {
         ret = min(ret, 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp));
      }
      return dp[i][j] = ret;
   }
   int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2){
      sort(arr2.begin(), arr2.end());
      int n = arr1.size();
      int m = arr2.size();
      vector<vector<int> > dp(2005, vector<int>(2005, -1));
      int ret = solve(arr1, arr2, 0, 0, INT_MIN, dp);
      return ret > arr2.size() ? -1 : ret - 1;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,5,3,7,8}, v1 = {1,3,2,5};
   cout << (ob.makeArrayIncreasing(v,v1));
}

入力

{1,5,3,7,8}, {1,3,2,5}

出力

1