Xây dựng mảng nơi bạn có thể tìm thấy các so sánh K chính xác tối đa trong C ++

Giả sử chúng ta có ba số nguyên n, m và k. Nếu chúng ta có thuật toán sau để tìm phần tử lớn nhất của một mảng các số nguyên dương -

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

Chúng ta phải tạo mảng arr có các tiêu chí sau:arr có đúng n số nguyên. tất cả các phần tử arr [i] nằm trong khoảng từ 1 đến m (bao gồm cả) (0 <=i

Vì vậy, nếu đầu vào là n =2, m =3, k =1, thì đầu ra sẽ là 6 vì các mảng có thể có là [1, 1], [2, 1], [2, 2], [3 , 1], [3, 2] [3, 3]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=10 ^ 9 + 7

• Xác định một hàm add (), điều này sẽ lấy a, b,

• return ((a mod m) + (b mod m)) mod m

• Xác định một mảng dp có kích thước:54 x 54 x 105.

• Xác định một hàm help (), hàm này sẽ nhận idx, m, k, currVal, n,

• nếu k <0, thì -

  • trả về 0

• nếu idx giống n + 1 thì -

  • trả về true khi k bằng 0

• nếu dp [idx, k, currVal + 1] không bằng -1 thì -

  • trả về dp [idx, k, currVal + 1]

• ret:=0

• để khởi tạo i:=1, khi i <=m, cập nhật (tăng i lên 1), thực hiện -

  • nếu tôi> currVal, thì -

    • ret:=add (help (idx + 1, m, k - 1, max (currVal, i), n), ret)

  • Nếu không

    • ret:=add (help (idx + 1, m, k, max (currVal, i), n), ret)

• trả về dp [idx, k, currVal + 1] =ret

• Từ phương thức chính, hãy làm như sau -

• để khởi tạo i:=0, khi tôi <54, hãy cập nhật (tăng i lên 1), thực hiện -

  • để khởi tạo j:=0, khi j <54, cập nhật (tăng j lên 1), thực hiện -

    • để khởi tạo k:=0, khi k <105, cập nhật (tăng k lên 1), thực hiện -

      • dp [i, j, k]:=-1

  • ret:=help (1, m, k, -1, n)

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơ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));
}

Đầu vào

2, 3, 1

Đầu ra

6