C++で正確にK個の最大の比較を見つけることができる配列を構築する

3つの整数n、m、およびkがあるとします。正の整数の配列の最大要素を見つけるために次のアルゴリズムがある場合-

max_val := -1
max_ind := -1
search_cost := 0
n := size of arr
for initialize i := 0, when i < n, update (increase i by 1), do:
   if max_val < arr[i], then:
      max_val := arr[i]
      max_ind := i
      (increase search_cost by 1)
return max_ind

次の基準を持つ配列arrを作成する必要があります。arrには正確にn個の整数があります。すべての要素arr[i]は1からm（含む）の範囲にあります（0 <=i

したがって、入力がn =2、m =3、k =1の場合、可能な配列は[1、1]、[2、1]、[2、2]、[3]であるため、出力は6になります。 、1]、[3、2] [3、3]

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

• m：=10 ^ 9 + 7

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）+（b mod m））mod m

• サイズの配列dpを定義します：54 x 54x105。

• 関数help（）を定義します。これには、idx、m、k、currVal、n、

  が必要です。

• k <0の場合、-

  • 0を返す

• idxがn+1と同じ場合、-

  • kが0の場合はtrueを返します

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

  • dp [idx、k、currVal + 1]

    を返します

• ret：=0

• 初期化i：=1の場合、i <=mの場合、更新（iを1増やします）、実行-

  • i> currValの場合、-

    • ret：=add（help（idx + 1、m、k --1、max（currVal、i）、n）、ret）

  • それ以外の場合

    • ret：=add（help（idx + 1、m、k、max（currVal、i）、n）、ret）

• dp [idx、k、currVal + 1] =ret

  を返します

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

• 初期化i：=0の場合、i <54の場合、更新（iを1増やします）、実行-

  • 初期化j：=0の場合、j <54の場合、更新（jを1増やします）、実行-

    • 初期化k：=0の場合、k <105の場合、更新（kを1増やします）、実行-

      • dp [i、j、k]：=-1

  • ret：=help（1、m、k、-1、n）

• retを返す

例

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

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
   lli add(lli a, lli b) {
      return ((a % m) + (b % m)) % m;
   }
   int dp[54][54][105];
   int help(int idx, int m, int k, int currVal, int n) {
      if (k < 0)
         return 0;
      if (idx == n + 1) {
         return k == 0;
      }
      if (dp[idx][k][currVal + 1] != -1)
         return dp[idx][k][currVal + 1];
      int ret = 0;
      for (int i = 1; i <= m; i++) {
         if (i > currVal) {
            ret = add(help(idx + 1, m, k - 1, max(currVal, i), n), ret);
         }
         else {
            ret = add(help(idx + 1, m, k, max(currVal, i), n), ret);
         }
      }
      return dp[idx][k][currVal + 1] = ret;
   }
   int numOfArrays(int n, int m, int k) {
      for (int i = 0; i < 54; i++)
         for (int j = 0; j < 54; j++)
            for (int k = 0; k < 105; k++)
               dp[i][j][k] = -1;
      int ret = help(1, m, k, -1, n);
      return ret;
   }
};
main() {
   Solution ob;
   cout << (ob.numOfArrays(2, 3, 1));
}

入力

2, 3, 1

出力

6