Tổng lớn nhất từ ba mảng sao cho không chọn liên tiếp từ cùng một mảng trong C++

Trong bài toán này, chúng ta được cung cấp ba mảng arr1[], arr2[], arr3[] cùng kích thước N. Nhiệm vụ là viết chương trình tìm tổng lớn nhất từ ba mảng sao cho không được chọn liên tiếp hai phần tử từ cùng một mảng trong C++.

Mô tả vấn đề

Ta tìm tổng lớn nhất bằng cách chọn N phần tử. Phần tử thứ i được chọn từ arr1[i], arr2[i] hoặc arr3[i]. Điều kiện: không được chọn hai phần tử liên tiếp từ cùng một mảng.

Ví dụ minh họa:

Đầu vào

arr1[] = {5, 8, 9, 20}, arr2[] = {7, 12, 1, 10}, arr3[] = {8, 9, 10, 11}, N = 4

Đầu ra

50

Giải thích

• i = 0: chọn 8 từ arr3
• i = 1: chọn 12 từ arr2
• i = 2: chọn 10 từ arr3
• i = 3: chọn 20 từ arr1

Tổng = 8 + 12 + 10 + 20 = 50

Phương pháp giải

Sử dụng quy hoạch động với ghi nhớ (memoization). Tạo ma trận 2D DP[][], trong đó DP[i][j] là tổng lớn nhất đến chỉ số i khi chọn từ mảng j. Đệ quy tính toán: tại mỗi bước, chọn từ mảng hiện tại sau đó gọi đệ quy cho hai mảng còn lại ở chỉ số tiếp theo.

Ví dụ chương trình

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

const int N = 3;

int findMaxVal(int a, int b) {
    if (a > b) return a;
    return b;
}

int FindMaximumSum(int index, int arrNo, int arr1[], int arr2[], int arr3[], int n, int DP[][N]) {
    if (index == n) return 0;
    if (DP[index][arrNo] != -1) return DP[index][arrNo];
    
    int maxVal = -1;
    if (arrNo == 0) {
        maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
        maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
    } else if (arrNo == 1) {
        maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
        maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
    } else if (arrNo == 2) {
        maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
        maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
    }
    return DP[index][arrNo] = maxVal;
}

int main() {
    int arr1[] = {5, 8, 9, 20};
    int arr2[] = {7, 12, 1, 10};
    int arr3[] = {8, 9, 10, 11};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int DP[n][N];
    memset(DP, -1, sizeof DP);
    
    int val1 = FindMaximumSum(0, 0, arr1, arr2, arr3, n, DP);
    int val2 = FindMaximumSum(0, 1, arr1, arr2, arr3, n, DP);
    int val3 = FindMaximumSum(0, 2, arr1, arr2, arr3, n, DP);
    
    cout << "Tổng lớn nhất từ 3 mảng không chọn liên tiếp từ cùng mảng: " 
         << findMaxVal(val1, findMaxVal(val2, val3));
    return 0;
}

Kết quả

Tổng lớn nhất từ 3 mảng không chọn liên tiếp từ cùng mảng: 50