数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告