Tổng trung bình lớn nhất khi phân hoạch mảng thành K nhóm trong C++

Đề bài

Cho mảng A, phân hoạch thành tối đa K nhóm liền kề không rỗng. Điểm số = tổng trung bình của mỗi nhóm. Tìm điểm số lớn nhất.

Ví dụ: A = {9,2,5,3,10}, K=3. Phân hoạch {9}, {2,5,3}, {10} → 9 + (10/3) + 10 = 22.33.

Thuật toán (Đệ quy + Memoization)

• memo[i][k]: điểm tốt nhất phân hoạch A[i..n-1] thành k nhóm.
• Thử mọi điểm cắt j: điểm = average(i, j-1) + memo[j][k-1].
• Cơ sở: k=1 → trung bình cả đoạn.

Ví dụ minh họa (C++)

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

#define MAX 1000
double memo[MAX][MAX];

double score(int n, vector<int>& arr, int k) {
    if (memo[n][k] > 0) return memo[n][k];
    double sum = 0;
    for (int i = n - 1; i > 0; i--) {
        sum += arr[i];
        memo[n][k] = max(memo[n][k], score(i, arr, k - 1) + sum / (n - i));
    }
    return memo[n][k];
}

double getLargestSum(vector<int>& arr, int K) {
    int n = arr.size();
    double sum = 0;
    memset(memo, 0, sizeof(memo));
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        memo[i + 1][1] = sum / (i + 1);
    }
    return score(n, arr, K);
}

int main() {
    vector<int> arr = {9, 2, 5, 3, 10};
    int K = 3;
    cout << "Tong trung binh lon nhat = " << getLargestSum(arr, K) << endl;
    return 0;
}

Kết quả

Tong trung binh lon nhat = 22.3333