ধরুন আমাদের দুটি স্ট্রিং A এবং B আছে এবং অন্য দুটি কস্ট ভ্যালু যেমন CostA এবং CostB আছে। A এবং B অভিন্ন করার জন্য আমাদের সর্বনিম্ন খরচ খুঁজে বের করতে হবে। আমরা স্ট্রিং থেকে অক্ষর মুছে ফেলতে পারি, স্ট্রিং A থেকে মুছে ফেলার খরচ হল CostA, এবং B স্ট্রিং থেকে মুছে ফেলার খরচ হল CostB। একটি স্ট্রিং থেকে সমস্ত অক্ষর সরানোর খরচ একই। ধরুন স্ট্রিং A =“wxyz”, B =“wyzx”, CostA হল 10 এবং CostB হল 20৷ সুতরাং আউটপুট হবে 30৷ যদি আমরা উভয় স্ট্রিং থেকে x মুছে ফেলি, তাহলে A এবং B অভিন্ন হবে৷ সুতরাং খরচ হল 10 + 20 =30।
এটি Longest Common Subsequence সমস্যার একটি পরিবর্তন। আমাদের A এবং B থেকে LCS এর দৈর্ঘ্য খুঁজে বের করতে হবে, তারপর A এবং B থেকে LCS দৈর্ঘ্য বিয়োগ করতে হবে, এইভাবে আমরা মুছে ফেলার জন্য অক্ষরের সংখ্যা পেতে পারি।
উদাহরণ
#include <iostream>
using namespace std;
bool isRepresentedInDDigits(int num, int d, int base) {
if (d==1 && num < base)
return true;
if (d > 1 && num >= base)
return isRepresentedInDDigits(num/base, --d, base);
return false;
}
bool checkNumber(int num, int d) {
// Check for all bases one by one
for (int base=2; base<=32; base++)
if (isRepresentedInDDigits(num, d, base))
return true;
return false;
}
int main() {
int num = 8;
int dig = 2;
if(checkNumber(num, dig))
cout << "Can be represented";
else
cout << "Can not be represented";
} আউটপুট
Can be represented
