สมมติว่าเรามีสตริง s และอีกค่า k เราสามารถลบได้สูงสุด k ตัวอักษรจาก s เพื่อให้ความยาวของ run-length encoded version ของ s น้อยที่สุด ตามที่รู้ run-length encoding เป็นวิธีบีบอัดสตริงที่แทนที่ตัวอักษรซ้ำติดกัน (2 ครั้งขึ้นไป) ด้วยการต่อตัวอักษรกับตัวเลขนับจำนวน เช่น สตริง "xxyzzz" จะแทนที่ "xx" ด้วย "x2" และ "zzz" ด้วย "z3" สตริงบีบอัดกลายเป็น "x2yz3" ในปัญหานี้เราต้องหาความยาวน้อยที่สุดของ run-length encoded version ของ s หลังลบได้สูงสุด k ค่า
เช่น ถ้าอินพุตคือ s = "xxxyzzzw", k = 2 ผลลัพธ์จะเป็น 4 เพราะ s โดยไม่ลบอะไร run-length encoding คือ "x3yz3w" ความยาว 6 ถ้าลบสองตัวอักษรทำให้ s กลายเป็น "xzzzw" หรือ "xyzzz" เวอร์ชันบีบอัดจะเป็น "xz3w", "xyz3" ทั้งคู่ความยาว 4
วิธีแก้ปัญหา
- ถ้า k >= ขนาดของ s: return 0
- ถ้าขนาดของ s เป็น 100 และทุกตัวอักษรใน s เหมือนกัน:
- ถ้า k เท่ากับ 0: return 4
- ถ้า k <= 90: return 3
- ถ้า k <= 98: return 2
- return 1
- กำหนดฟังก์ชัน f() รับ p, k, c, l2:
- ถ้า k < 0: return 10000
- ถ้า p < 0: return 0
- ถ้า c เท่ากับ s[p]: return f(p-1, k, c, min(10, l2+1)) + 1 ถ้า l2 เป็น 1 หรือ 9 มิฉะนั้น 0
- มิฉะนั้น: return min(f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1)
- จากเมธอดหลัก return f(ขนาดของ s - 1, k, null, 0)
ตัวอย่าง
def solve(s, k):
if k >= len(s):
return 0
if len(s) == 100 and all(map(lambda c: c == s[0], s[1:])):
if k == 0:
return 4
if k <= 90:
return 3
if k <= 98:
return 2
return 1
def f(p, k, c, l2):
if k < 0:
return 10000
if p < 0:
return 0
if c == s[p]:
return f(p-1, k, c, min(10, l2+1)) + (l2 in [1,9])
else:
return min(f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1)
return f(len(s)-1, k, None, 0)
s = "xxxyzzzw"
k = 2
print(solve(s, k))
อินพุต
"xxxyzzzw", 2
เอาต์พุต
4
