C++에서 정확히 최대 K개 비교를 찾을 수 있는 배열 구축

<시간/>

세 개의 정수 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() 함수를 정의하면, b,
return ((a mod m) + (b mod m)) mod m
54 x 54 x 105 크기의 배열 dp를 정의합니다.
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
주요 방법에서 다음을 수행하십시오 -
initialize i :=0의 경우, i <54일 때 업데이트(i를 1만큼 증가), 수행 -
- initialize j :=0의 경우 j <54일 때 업데이트(j를 1만큼 증가), −
  - 초기화 k :=0의 경우 k <105일 때 업데이트(k를 1만큼 증가), 수행 -
    - dp[i, j, k] :=-1
- ret :=help(1, m, k, -1, n)
리턴 렛

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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