অ্যারে তৈরি করুন যেখানে আপনি 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-এর ঠিক n পূর্ণসংখ্যা রয়েছে। সমস্ত উপাদান arr[i] রেঞ্জ 1 থেকে m(সহ) (0 <=i

সুতরাং, যদি ইনপুটটি n =2, m =3, k =1 এর মত হয়, তাহলে আউটপুট 6 হবে কারণ সম্ভাব্য অ্যারেগুলি হল [1, 1], [2, 1], [2, 2], [3 , 1], [3, 2] [3, 3]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

m :=10^9 + 7
একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,
লাগবে
ফিরুন ((a mod m) + (b mod m)) mod m
আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন:54 x 54 x 105।
একটি ফাংশন সাহায্য(), এটি 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 :=সাহায্য(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