Vacation

Vacation

Atcoder easy

Given three arrays \(a\), \(b\), and \(c\) of integers, each of length \(N\), you need to select one element from each index \(i\) (where \(0 \le i < N\)) from either \(a_i\), \(b_i\), or \(c_i\).

Constraint: For every index \(i\) (where \(0 \le i < N - 1\)), the elements chosen at indices \(i\) and \(i + 1\) must come from different arrays.

Determine and print the maximum possible sum achievable under this constraint.

Note

To simplify the problem, we will represent the three arrays \(a\), \(b\), and \(c\) as a single 2D array \(d\) with dimensions \(N \times 3\).
Here, the first dimension is of length \(N\), and the second dimension is of length \(3\), where \(d_i\) is an array containing the values \([a_i, b_i, c_i]\).

Solution

We will solve this problem using dynamic programming.

Let’s define the state:

\(f(i, type)\) is the maximum sum possible if we consider the first i elements and at index i we choose d[i][type].

Next we’ll define the transition. There are three different transitions based on the \(type\)

\(f(i , 0) = max(f(i - 1, 1) , f(i - 1, 2)) + d_{i,0}\)

\(f(i , 1) = max(f(i - 1, 0) , f(i - 1, 2)) + d_{i,1}\)

\(f(i , 2) = max(f(i - 1, 0) , f(i - 1, 1)) + d_{i,2}\)

Our base case will be:

\(f(0, type) = d_{0,type}\)

The space complexity of the algorithm is determined by the number of states, which is \(O(N)\).

The time complexity is the number of states \(N\) multiplied by the complexity of each transition \(O(1)\), so the overall time complexity is \(O(N)\) as well.

#include <iostream>
using namespace std;

int dp[200000][3];
int d[200000][3];


int f (int i, int type) {
  
    if (i == 0) {
        return d[i][type];
    }

    if (dp[i][type] != -1) {
        return dp[i][type];
    }

  if(type == 0){
    dp[i][type] = max(f(i - 1, 1), f(i - 1, 2)) + d[i][type];
  }
  else if(type == 1){
    dp[i][type] = max(f(i - 1, 0), f(i - 1, 2)) + d[i][type];
  }
  else if(type == 2){
    dp[i][type] = max(f(i - 1, 0), f(i - 1, 1)) + d[i][type];
  }

    return dp[i][type];
}


int main() {
  
    for (int i = 0; i < 200000; i++) {
    for (int j = 0; j < 3; j++) {
          dp[i][j] = -1;
    }
    }

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> d[i][j];
    }
    }

    cout << max(max(f(n - 1, 0), f(n - 1, 1)), f(n - 1, 2)) << "\n";
}