資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式找出給定整數的最大可能總和
假設，我們給定兩個整數n和m，並且有k個整數元組，每個元組包含四個整數{ai, bi, ci, di}。給出四個陣列a、b、c、d，其中a[i]表示第i個元組的a值。現在，讓我們考慮一個序列dp，它有n個正整數，並且1 <= dp[1] < dp[2] < ..... < dp[n] <= m。我們定義一個度量“總和”。度量總和是在所有索引i上d[i]的總和，其中dp[b[i]] − dp[a[i]] = c[i]。如果沒有這樣的i，則總和為0。我們必須找出dp的最大可能總和。
因此，如果輸入類似於n = 4，m = 5，k = 4，a = {2, 2, 3, 5}，b = {4, 3, 4, 6}，c = {4, 3, 3, 4}，d = {110, 20, 20, 40}，則輸出將為130。
步驟
為了解決這個問題，我們將遵循以下步驟：
Define arrays A, B, C, D, and dp of sizes: 100, 100, 100, 100, 10 respectively. Define a function depthSearch(), this will take c, l, if c is same as n, then: total := 0 for initialize i := 0, when i < k, update (increase i by 1), do: if dp[B[i]] - dp[A[i]] is same as C[i], then: total := total + D[i] res := maximum of res and total return for initialize j := l, when j <= m, update (increase j by 1), do: dp[c] := j depthSearch(c + 1, j) for initialize i := 0, when i < k, update (increase i by 1), do: A[i] := a[i], B[i] := b[i], C[i] := c[i], D[i] := d[i] decrease A[i] by 1 decrease B[i] by 1 depthSearch(0, 1) return res
示例
讓我們看看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
int n, m, k, res = 0;
int A[100], B[100], C[100], D[100], dp[10];
void depthSearch(int c, int l){
if(c == n){
int total = 0;
for(int i = 0; i < k; i++) {
if(dp[B[i]] - dp[A[i]] == C[i]) total += D[i];
}
res = max(res, total);
return;
}
for(int j = l; j <= m; j++){
dp[c] = j;
depthSearch(c + 1, j);
}
}
int solve(int a[], int b[], int c[], int d[]){
for(int i = 0; i < k; i++){
A[i] = a[i], B[i] = b[i], C[i] = c[i], D[i] = d[i]; A[i]--, B[i]--;
}
depthSearch(0, 1);
return res;
}
int main() {
n = 4, m = 5, k = 4;
int a[] = {2, 2, 3, 5}, b[] = {4, 3, 4, 6}, c[] = {4, 3, 3, 4}, d[] = {110, 20, 20, 40};
cout<< solve(a, b, c, d);
return 0;
}輸入
4, 5, 4, {2, 2, 3, 5}, {4, 3, 4, 6}, {4, 3, 3, 4}, {110, 20, 20, 40}
輸出
130
更新於: 2022年3月2日
281 次檢視
廣告