ধরুন আমাদের দুটি স্ট্রিং A এবং B, এবং দুটি খরচ মান CostA, CostB আছে। আমাদের A এবং B কে অভিন্ন করার ন্যূনতম খরচ বের করতে হবে। স্ট্রিং থেকে ক্যারেক্টার ডিলিট করা যাবে, স্ট্রিং A থেকে ডিলিট করার খরচ CostA, এবং স্ট্রিং B থেকে ডিলিট করার খরচ CostB। একটি স্ট্রিং থেকে সব ক্যারেক্টার রিমুভ করার খরচ একই। ধরুন A = "wxyz", B = "wyzx", CostA = 10, CostB = 20। আউটপুট ৩০। যদি x উভয় স্ট্রিং থেকে ডিলিট করি, তবে A এবং B অভিন্ন হয়ে যাবে। তাই খরচ ১০ + ২০ = ৩০।
এটি লংগেস্ট কমন সাবসিকোয়েন্স (LCS) সমস্যার একটি ভ্যারিয়েশন। আমাদের 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
