মান লিজিয়ে, দুটি পূর্ণসংখ্যা 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 না থাকে, তবে ট্যালি ০। আমাদের লক্ষ্য হলো 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।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
A, B, C, D, dp অ্যারে সংজ্ঞায়িত করুন আকার: 100, 100, 100, 100, 10। depthSearch() ফাংশন সংজ্ঞায়িত করুন, যা c, l গ্রহণ করবে: if c == n, তবে: total := 0 i := 0 থেকে k-1 পর্যন্ত: if dp[B[i]] - dp[A[i]] == C[i], তবে: total := total + D[i] res := max(res, total) return 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
