สร้างอาร์เรย์ที่คุณสามารถค้นหาการเปรียบเทียบ K สูงสุดใน C++

สมมติว่าเรามีจำนวนเต็มสามจำนวน 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 ดังนั้นเอาต์พุตจะเป็น 6 เนื่องจากอาร์เรย์ที่เป็นไปได้คือ [1, 1], [2, 1], [2, 2], [3 , 1], [3, 2] [3, 3]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=10^9 + 7

• กำหนดฟังก์ชัน add() ซึ่งจะใช้เวลา a, b,

• กลับ ((a mod m) + (b mod m)) mod m

• กำหนดขนาดอาร์เรย์ dp:54 x 54 x 105

• กำหนดฟังก์ชัน help() ซึ่งจะใช้ idx, m, k, currVal, n,

• ถ้า k <0 แล้ว −

  • คืนค่า 0

• ถ้า idx เหมือนกับ n + 1 แล้ว −

  • คืนค่าจริงเมื่อ k เป็น 0

• ถ้า dp[idx, k, currVal + 1] ไม่เท่ากับ -1 แล้ว −

  • ส่งคืน dp[idx, k, currVal + 1]

• ยกเลิก :=0

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=m อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ถ้าฉัน> 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)

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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