ধরুন আমাদের স্কোর এবং বয়স নামে দুটি তালিকা রয়েছে, যেখানে স্কোর[i] এবং বয়স[i] একটি বাস্কেটবল খেলায় ith খেলোয়াড়ের স্কোর এবং বয়সকে প্রতিনিধিত্ব করে। আমরা সর্বোচ্চ সার্বিক স্কোর নিয়ে দল নির্বাচন করতে চাই। এখানে দলের স্কোর হল দলের সকল খেলোয়াড়ের মোট স্কোরের যোগফল। কিন্তু আমরা খেলায় সংঘাতের অনুমতি দিই না। এখানে একটি দ্বন্দ্ব বিদ্যমান যদি একজন অল্প বয়স্ক খেলোয়াড়ের একটি বয়স্ক খেলোয়াড়ের চেয়ে কঠোরভাবে বেশি স্কোর থাকে।
সুতরাং, যদি ইনপুট হয় স্কোর =[5,7,9,14,19], বয়স =[5,6,7,8,9], তাহলে আউটপুট হবে 54 কারণ আমরা সমস্ত খেলোয়াড় নির্বাচন করতে পারি।পি>
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- sa :=যুগ ও স্কোর থেকে যথাক্রমে a এবং s উপাদান নিয়ে গঠিত জোড়ার একটি তালিকা
- তালিকা বাছাই করুন
- স্কোর :=sa থেকে স্কোরের একটি তালিকা তৈরি করুন
- maxScore :=0
- n :=স্কোরের আকার
- dp :=দৈর্ঘ্যের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
- আমি 0 থেকে n - 1 রেঞ্জের জন্য, কর
- স্কোর :=স্কোর[i]
- dp[i] :=স্কোর 0 থেকে i - 1 রেঞ্জের মধ্যে j-এর জন্য
- করুন
- যদি স্কোর হয়[j] <=স্কোর, তাহলে
- dp[i] :=সর্বাধিক dp[i] এবং dp[j] + স্কোর
- যদি স্কোর হয়[j] <=স্কোর, তাহলে
- maxScore :=সর্বোচ্চ maxScore এবং dp[i]
- ম্যাক্সস্কোর ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
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]
আউটপুট
54