数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法律研究在C++中构建可在恰好K次比较中找到最大值的数组
假设我们有三个整数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
定义一个大小为54 x 54 x 105的数组dp。
定义一个函数help()，它将接收idx、m、k、currVal、n，
如果k < 0，则：
返回0
如果idx等于n + 1，则：
当k为0时返回true
如果dp[idx, k, currVal + 1]不等于-1，则：
返回dp[idx, k, currVal + 1]
ret := 0
对于初始化i := 1，当i <= m时，更新（i增加1），执行：
如果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
从主方法执行以下操作：
对于初始化i := 0，当i < 54时，更新（i增加1），执行：
对于初始化j := 0，当j < 54时，更新（j增加1），执行：
对于初始化k := 0，当k < 105时，更新（k增加1），执行：
dp[i, j, k] := -1
ret := help(1, m, k, -1, n)
返回ret
示例
让我们看看下面的实现以更好地理解：
#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
输出
6
浏览量：113
