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

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm số chuỗi con có sản phẩm nhỏ hơn K.

Đối với điều này, chúng tôi sẽ được cung cấp với mảng không âm và một giá trị k. Nhiệm vụ của chúng ta là tìm tất cả các dãy con trong mảng có tích nhỏ hơn k.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
//counting subsequences with product
//less than k
int count_sub(vector<int> &arr, int k){
   int n = arr.size();
   int dp[k + 1][n + 1];
   memset(dp, 0, sizeof(dp));
   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;
   A.push_back(1);
   A.push_back(2);
   A.push_back(3);
   A.push_back(4);
   int k = 10;
   cout << count_sub(A, k) << endl;
}

Đầu ra

11