資料結構
網路
關係資料庫管理系統 (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
