4 Keys Keyboard – หาจำนวน A สูงสุดจาก 4 ปุ่มใน C++

ปัญหา: 4 Keys Keyboard

มี 4 ปุ่ม: A (พิมพ์ A), Ctrl+A (Select All), Ctrl+C (Copy), Ctrl+V (Paste)
กำหนดจำนวนครั้งที่กดปุ่ม N หา จำนวน A สูงสุด ที่ได้

ตัวอย่าง

N = 7 → Output: 9

Sequence: A, A, A, Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V
→ 3 A → Select All → Copy → Paste → Paste = 3 × 3 = 9

แนวทางแก้ปัญหา: Dynamic Programming

ข้อสังเกต

• ลำดับ optimal จะเป็น: พิมพ์ A จำนวนหนึ่ง → (Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V, ...) ซ้ำ
• จุดหยุด (breakpoint) = จุดที่กด Ctrl+A, Ctrl+C แล้ว Paste ซ้ำ
• สำหรับ N ≤ 6: กด A ทุกครั้งดีที่สุด (N ตัว)
• สำหรับ N ≥ 7: ลอง breakpoint ทุกตำแหน่ง

Recurrence

dp[n] = max_{b=1..n-3} ( (n - b - 1) * dp[b] )

• b = จำนวน keystrokes ก่อน Ctrl+A, Ctrl+C (ต้องเหลือ ≥ 3 สำหรับ A,C,V)
• n - b - 1 = จำนวนครั้งที่ Paste (หลังจาก A,C แล้วเหลือ n-b-2 ครั้ง, แต่ Paste ครั้งแรกรวมใน n-b-1)
• จริงๆ: ใช้ b keystrokes ได้ dp[b] A's, แล้ว (Ctrl+A, Ctrl+C) 2 ครั้ง, เหลือ n-b-2 ครั้งสำหรับ Paste → รวม (n-b-1) * dp[b]

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int maxA(int keystrokes) {
    if (keystrokes <= 6) return keystrokes;

    vector<int> dp(keystrokes + 1);
    for (int i = 1; i <= 6; i++) dp[i] = i;

    for (int n = 7; n <= keystrokes; n++) {
        dp[n] = 0;
        for (int b = n - 3; b >= 1; b--) {
            int curr = (n - b - 1) * dp[b];
            dp[n] = max(dp[n], curr);
        }
    }
    return dp[keystrokes];
}

int main() {
    for (int n = 1; n <= 10; n++)
        cout << "N=" << n << ": " << maxA(n) << '\n';
    // N=7: 9, N=8: 12, N=9: 16, N=10: 20
    return 0;
}

ตารางคำตอบสำหรับ N = 1..10

ความซับซ้อน

• เวลา: O(N²) – น้อยพอสำหรับ N ≤ 50 (typical constraint)
• พื้นที่: O(N)

ข้อสังเกต

• LeetCode 651 (4 Keys Keyboard)
• Pattern: หลัง N=6, คำตอบเติบโตแบบคูณ (ประมาณ ×1.5 ต่อ 3 keystrokes)
• Optimal strategy: หา breakpoint ที่ maximize (n-b-1) * dp[b]
• โค้ดต้นฉบับมีบั๊กเล็กน้อยใน main (อ่าน input ผิด) – โค้ดข้างต้นแก้ไขแล้ว