Đếm tất cả dãy con có tích nhỏ hơn K trong C++

Trong hướng dẫn này, ta sẽ thảo luận chương trình để tìm số lượng dãy con (subsequence) có tích nhỏ hơn K.

Cho mảng không âm và giá trị K. Nhiệm vụ là tìm tất cả dãy con có tích nhỏ hơn K.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int count_sub(vector<int> &arr, int k) {
    int n = arr.size();
    vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
    for(int i = 1; i <= k; i++) {
        for(int j = 1; j <= n; j++) {
            dp[i][j] = dp[i][j - 1];
            if(arr[j - 1] <= i && arr[j - 1] > 0)
                dp[i][j] += dp[i / arr[j - 1]][j - 1] + 1;
        }
    }
    return dp[k][n];
}

int main() {
    vector<int> A = {1, 2, 3, 4};
    int k = 10;
    cout << count_sub(A, k) << endl;
    return 0;
}

Kết quả

11