พิมพ์ 'A' ให้ได้มากที่สุดด้วย 4 ปุ่ม (A, Ctrl+A, Ctrl+C, Ctrl+V)

มีคีย์บอร์ด 4 ปุ่ม: 'A', Ctrl+A (Select All), Ctrl+C (Copy), Ctrl+V (Paste)

เป้าหมาย: กดปุ่มทั้งหมด N ครั้ง ให้ได้ตัว 'A' มากที่สุด

ตัวอย่าง Input และ Output

Input: N = 7
Output: Maximum Number of A's with 7 keystrokes is: 9
วิธีทำ: กด A 3 ครั้ง → Ctrl+A → Ctrl+C → Ctrl+V → Ctrl+V
(3 + 1 + 1 + 1 + 1 = 7 ครั้ง, ได้ 3 × 3 = 9 ตัว A)

อัลกอริทึม Dynamic Programming

ฟังก์ชัน keyNumbers(keyStrokes)

สังเกตสำคัญ:

• N ≤ 6: กด 'A' ทุกครั้งดีที่สุด (เพราะต้องใช้ 3 ครั้งสำหรับ Ctrl+A, C, V จึงคุ้มค่าเมื่อ N ≥ 7)
• N ≥ 7: ลองหา breakpoint - จุดที่เริ่มทำ Select-Copy-Paste

ขั้นตอน:

1. ถ้า keyStrokes <= 6 → คืน keyStrokes
2. สร้างอาร์เรย์ result[n] เก็บคำตอบสำหรับ 1..n ครั้ง
3. เติม result[i] = i+1 สำหรับ i = 0..5 (N=1..6)
4. สำหรับ n = 7 ถึง keyStrokes:
   • result[n-1] = 0
   • ลอง breakpoint = n-3 ถึง 1 (ต้องเหลืออย่างน้อย 3 ครั้งสำหรับ Ctrl+A, C, V)
   • จำนวน Paste = n - breakpoint - 1
   • ค่าที่ได้ = (n - breakpoint - 1) * result[breakpoint - 1]
   • อัปเดต result[n-1] ด้วยค่าสูงสุด
5. คืน result[keyStrokes - 1]

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

#include <iostream>
#include <algorithm>
using namespace std;

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

    int result[keystrokes];
    for (int n = 1; n <= 6; n++)
        result[n-1] = n;

    for (int n = 7; n <= keystrokes; n++) {
        result[n-1] = 0;
        for (int breakPoint = n-3; breakPoint >= 1; breakPoint--) {
            int curr = (n - breakPoint - 1) * result[breakPoint - 1];
            if (curr > result[n-1])
                result[n-1] = curr;
        }
    }
    return result[keystrokes-1];
}

int main() {
    int keystrokes;
    cout << "Enter Number of keystrokes: "; cin >> keystrokes;
    cout << "Maximum Number of A's with " << keystrokes 
         << " keystrokes is: " << keyNumbers(keystrokes) << endl;
    return 0;
}

Output

Enter Number of keystrokes: 7
Maximum Number of A's with 7 keystrokes is: 9

ตารางคำตอบสำหรับ N ต่างๆ

ความซับซ้อน

• Time: O(N²)
• Space: O(N)