Tìm kích thước mảng nhỏ nhất sau khi xóa theo quy tắc trong C++

Giới thiệu

Cho mảng n số và số k. Có thể xóa 3 phần tử liền kề nếu chúng tạo cấp số cộng công sai k (arr[i+1]=arr[i]+k, arr[i+2]=arr[i+1]+k). Tìm kích thước nhỏ nhất có thể đạt được sau các phép xóa.

Ví dụ minh họa

Đầu vào

{4, 6, 8, 4, 1, 5}, k = 2

Đầu ra

3

Giải thích

Xóa được nhóm (4,6,8) tại chỉ số 0,1,2. Mảng còn {4,1,5} kích thước 3.

Phương pháp giải: Quy hoạch động với memoization - O(N³)

Định nghĩa DP[l][r] = kích thước nhỏ nhất của mảng con từ l đến r sau xóa tối ưu. Cơ sở: độ dài < 3 ⇒ không xóa được. Chuyển trạng thái: Thử xóa triplet (l, i, j) thỏa mãn điều kiện, nếu phần giữa có thể xóa hết (DP=0) thì DP[l][r] = min(DP[l][r], DP[j+1][r]).

Chương trình minh họa

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

#define MAX 1000
int DP[MAX][MAX];

int calcMinSize(int arr[], int l, int r, int k) {
    if (DP[l][r] != -1) return DP[l][r];
    if (r - l + 1 < 3) return r - l + 1;
    
    int minSize = 1 + calcMinSize(arr, l+1, r, k); // Không xóa arr[l]
    
    for (int i = l+1; i <= r-1; i++) {
        for (int j = i+1; j <= r; j++) {
            if (arr[i] == arr[l] + k && arr[j] == arr[l] + 2*k &&
                calcMinSize(arr, l+1, i-1, k) == 0 &&
                calcMinSize(arr, i+1, j-1, k) == 0) {
                minSize = min(minSize, calcMinSize(arr, j+1, r, k));
            }
        }
    }
    return DP[l][r] = minSize;
}

int main() {
    int arr[] = {4, 6, 8, 4, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 2;
    memset(DP, -1, sizeof(DP));
    cout << "Minimum possible size after removals: " << calcMinSize(arr, 0, n-1, k);
    return 0;
}

Đầu ra

Minimum possible size of the array after removal is 3