Xây dựng mảng tìm giá trị lớn nhất chính xác K lần so sánh trong C++

Cho ba số nguyên n, m, k. Có thuật toán sau để tìm phần tử lớn nhất của mảng số nguyên dương:

max_val := -1
max_ind := -1
search_cost := 0
n := size of arr
for i := 0 to n-1:
    if max_val < arr[i]:
        max_val := arr[i]
        max_ind := i
        search_cost := search_cost + 1
return max_ind

Ta cần xây dựng mảng arr thỏa mãn:

• arr có đúng n số nguyên
• Mọi phần tử arr[i] nằm trong khoảng 1 đến m
• Sau khi chạy thuật toán, search_cost = k

Tìm số cách xây dựng mảng như vậy. Kết quả lấy modulo 10^9 + 7.

Ví dụ: n = 2, m = 3, k = 1 → Kết quả = 6. Các mảng: [1,1], [2,1], [2,2], [3,1], [3,2], [3,3]

Phương pháp giải

Sử dụng quy hoạch động 3 chiều dp[idx][k][currVal]. Hàm đệ quy help(idx, m, k, currVal, n) tính số cách từ vị trí idx với chi phí tìm kiếm còn lại k và giá trị lớn nhất hiện tại currVal.

Ví dụ chương trình

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;

class Solution {
public:
    lli add(lli a, lli b) {
        return ((a % MOD) + (b % MOD)) % MOD;
    }
    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;
        return help(1, m, k, -1, n);
    }
};

int main() {
    Solution ob;
    cout << ob.numOfArrays(2, 3, 1);
    return 0;
}

Đầu vào

2, 3, 1

Đầu ra

6