สมมติว่าเรามีสองสตริง 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
นี่เป็นหนึ่งในรูปแบบของปัญหาลำดับรองที่ยาวที่สุด เราต้องหาความยาวของ LCS จาก A และ B แล้วลบความยาว LCS ออกจาก A และ B เราจะได้จำนวนอักขระที่จะลบออก
ตัวอย่าง
#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
