C++ এ আনক্রসড লাইন

ধরুন আমরা দুটি পৃথক অনুভূমিক রেখায় A এবং B এর পূর্ণসংখ্যা (যে ক্রমে দেওয়া হয়েছে) লিখেছি। এখন, আমরা সংযোগকারী রেখা আঁকতে পারি:একটি সরল রেখা দুটি সংখ্যা A[i] এবং B[j] কে সংযুক্ত করে যাতে −

• A[i] ==B[j];

• আমরা যে রেখা আঁকি তা অন্য কোনো সংযোগকারী (অ-অনুভূমিক) রেখাকে ছেদ করে না।

আমাদের মনে রাখতে হবে যে সংযোগকারী লাইনগুলি এমনকি শেষ বিন্দুতেও ছেদ করতে পারে না - প্রতিটি সংখ্যা শুধুমাত্র একটি সংযোগ লাইনের অন্তর্গত হতে পারে। সংযোগ লাইনের সর্বাধিক সংখ্যা খুঁজুন। সুতরাং ইনপুট যদি [1,4,2] এবং [1,2,4] এর মত হয়, তাহলে আউটপুট হবে 2।

আমরা ডায়াগ্রামের মতো 2টি আনক্রসড লাইন আঁকতে পারি। আমরা 3টি আনক্রস করা লাইন আঁকতে পারি না, এর কারণ হল A[1]=4 থেকে B[2]=4 লাইনটি A[2]=2 থেকে B[1]=2 রেখাকে ছেদ করবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• সমাধান() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি নেবে, i, j, অ্যারে A, অ্যারে B এবং ম্যাট্রিক্স dp

• যদি আমি অ্যারের রেঞ্জের বাইরে থাকি তবে 0

  ফেরত দিন

• যদি j অ্যারে B এর রেঞ্জের বাইরে থাকে, তাহলে 0

  ফেরত দিন

• nj :=j

• যখন nj নয়

  • 1 দ্বারা nj বাড়ান

• temp :=1 যখন nj

• ret :=সর্বাধিক (সল্ভ(i + 1, j, A, B, dp) এবং temp) + সমাধান(i + 1, nj + 1, A, B, dp)

• dp[i, j] :=ret এবং রিটার্ন ret

• মূল পদ্ধতি থেকে

• n :=A এর আকার, m :=B এর আকার

• n x m আকারের একটি ম্যাট্রিক্স ডিপি তৈরি করুন এবং এটি – 1

  দিয়ে পূরণ করুন

• কল সমাধান (0, 0, A, , dp)

#include নেমস্পেস ব্যবহার করে std;class Solution { public:int solve(int i, int j, ভেক্টর &A, ভেক্টর &B, ভেক্টর <ভেক্টর >&dp){ if(i>=A.size()) রিটার্ন 0; if(j>=B.size()) রিটার্ন 0; if(dp[i][j] !=-1) রিটার্ন dp[i][j]; int nj =j; while(nj &A, vector&B) { int n =A.size(); int m =B.size(); ভেক্টর <ভেক্টর > dp(n, ভেক্টর (m, -1)); রিটার্ন সলভ (0, 0, A, B, dp); }};প্রধান(){ ভেক্টর v1 ={1,4,2}; ভেক্টর v2 ={1,2,4}; সমাধান ob; cout <<(ob.maxUncrossedLines(v1, v2));}

2