在本教程中,我们将讨论一个程序,以查找乘积小于K的子序列数。
为此,我们将提供非负数组和值k。我们的任务是找到乘积小于k的数组中的所有子序列。
#include <bits/stdc++.h> using namespace std; //用产品计算子序列 //小于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; }
输出结果
11