मान लीजिए हमें दो पूर्णांक 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 होगा।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
आकार 100 के सरणी A, B, C, D और आकार 10 के सरणी dp परिभाषित करें
एक फंक्शन depthSearch() परिभाषित करें जो c, l लेता है:
यदि c == n, तो:
total := 0
i := 0 से k-1 तक:
यदि dp[B[i]] - dp[A[i]] == C[i], तो:
total := total + D[i]
res := max(res, total)
लौटें
j := l से m तक:
dp[c] := j
depthSearch(c + 1, j)
i := 0 से k-1 तक:
A[i] := a[i], B[i] := b[i], C[i] := c[i], D[i] := d[i]
A[i] घटाएँ, B[i] घटाएँ
depthSearch(0, 1)
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