পাইথনে কনফ্লিক্ট-ফ্রি 베স্ট টিম খুঁজে বের করার প্রোগ্রাম

মান লিজিয়ে দুটি লিস্ট আছে scores এবং ages, যেখানে scores[i] এবং ages[i] হল i-তম খেলোয়াড়ের স্কোর এবং বয়স। আমরা সর্বোচ্চ মোট স্কোর वाली টিম বানাতে চাই। টিমের স্কোর হল সব খেলোয়াড়ের স্কোরের যোগফল। কিন্তু কনফ্লিক্ট অনুমোদন নেই। কনফ্লিক্ট হয় যদি কম বয়সের খেলোয়াড় বয়স্ক খেলোয়াড়ের চেয়ে স্ট্রিক্টলি বেশি স্কোর পায়।

যেমন, ইনপুট হলে scores = [5,7,9,14,19], ages = [5,6,7,8,9], তবে আউটপুট হবে 54 কারণ সব খেলোয়াড় নেওয়া যায়।

সমাধানের ধাপসমূহ

sa := [(a,s) for a,s in zip(ages,scores)]
sa.sort()
scores := [s for a,s in sa]
maxScore := 0, n := len(scores)
dp := [0]*n
i = 0 থেকে n-1 পর্যন্ত:
- score := scores[i], dp[i] := score
- j = 0 থেকে i-1 পর্যন্ত:
  - যদি scores[j] <= score হয়, তবে dp[i] = max(dp[i], dp[j] + score)
- maxScore = max(maxScore, dp[i])
maxScore রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(scores, ages):
    sa = [[a, s] for a, s in zip(ages, scores)]
    sa.sort()
    scores = [s for a, s in sa]
    maxScore = 0
    n = len(scores)
    dp = [0] * n
    for i in range(n):
        score = scores[i]
        dp[i] = score
        for j in range(i):
            if scores[j] <= score:
                dp[i] = max(dp[i], dp[j] + score)
        maxScore = max(maxScore, dp[i])
    return maxScore

scores = [5,7,9,14,19]
ages = [5,6,7,8,9]
print(solve(scores, ages))

ইনপুট

[5,7,9,14,19], [5,6,7,8,9]