สร้างอาร์เรย์ที่หาค่าสูงสุดได้พอดี 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) หลังจากใช้อัลกอริทึมข้างต้นกับ arr ค่า search_cost จะต้องเท่ากับ k เราต้องหาจำนวนวิธีในการสร้างอาร์เรย์ arr ภายใต้เงื่อนไขที่กล่าวมา คำตอบอาจใหญ่มาก จึงคำนวณโมดิวโล 10^9 + 7

เช่น ถ้าอินพุตคือ 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
กำหนดอาร์เรย์ dp ขนาด 54 x 54 x 105
กำหนดฟังก์ชัน help() รับ idx, m, k, currVal, n
ถ้า k < 0 คืนค่า 0
ถ้า idx เท่ากับ n + 1 คืนค่า true เมื่อ k เป็น 0
ถ้า dp[idx, k, currVal + 1] ไม่เท่ากับ -1 คืนค่า dp[idx, k, currVal + 1]
ret := 0
ลูป i จาก 1 ถึง m: ถ้า 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
จาก main method: เริ่มต้น dp ด้วย -1 แล้วเรียก 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

สร้างอาร์เรย์ที่หาค่าสูงสุดได้พอดี K ครั้งใน C++

ตัวอย่าง

อินพุต

เอาต์พุต