Bàn phím 4 phím trong C++

Giới thiệu

Có 4 phím: 'A', 'Ctrl+A' (chọn tất), 'Ctrl+C' (copy), 'Ctrl+V' (paste). Cho số lần nhấn phím N, tìm số lượng chữ 'A' tối đa có thể in ra.

Quan sát

• Với N ≤ 6: chỉ nên nhấn 'A' → N chữ A.
• Với N ≥ 7: tối ưu là chọn một breakpoint (điểm ngắt) để thực hiện: [A...A] [Ctrl+A, Ctrl+C] [Ctrl+V...Ctrl+V].
• Số A = (số A trước breakpoint) * (số lần paste + 1).

Đệ quy quy hoạch động

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

Cài đặt 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() {
    int n;
    cout << "Nhap so lan nhan phim: "; cin >> n;
    cout << "So 'A' toi da: " << maxA(n) << endl;
    // Ví dụ: n=7 -> 9 (AAA, Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V)
    return 0;
}

Bảng giá trị nhỏ

Độ phức tạp

• Thời gian: O(N²).
• Không gian: O(N).

LeetCode 651 "4 Keys Keyboard".