Độ phức tạp: ~O(N)~

Gọi dp[i][j] (~i: 1 \rightarrow n, j: 0 \rightarrow 2~ đại diện cho các hoạt động ~A~, ~B~, ~C~) là số điểm hạnh phúc tối đa mà Taro có thể nhận được khi tham gia các hoạt động trong ~i~ ngày đầu tiên mà hoạt động thực hiện vào ngày thứ ~i~ là hoạt động ~j~. Với điều kiện Taro không thể thực hiện các hoạt động giống nhau trong hai hoặc nhiều ngày liên tiếp, ví dụ như vào ngày thứ ~i~, Taro muốn tham gia hoạt động ~A~, thì ngày thứ ~i-1~, Taro chỉ có thể thực hiện các hoạt động ~B~ hoặc ~C~ nên ta có công thức QHĐ sau:

Với dp[i][j] khởi tạo nhận giá trị bằng ~0~. Kết quả cần tìm chính là ~max(dp[N][0],~ ~dp[N][1],~ ~dp[N][2]).~

#include <bits/stdc++.h>

using namespace std;

const int mx = 1e5 + 11;

int dp[mx][3];

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int N; cin >> N;

    for(int i = 1; i <= N; ++i) {
        int a, b, c; cin >> a >> b >> c;
        dp[i][0] = max(dp[i - 1][1] + a, dp[i - 1][2] + a);
        dp[i][1] = max(dp[i - 1][0] + b, dp[i - 1][2] + b);
        dp[i][2] = max(dp[i - 1][0] + c, dp[i - 1][1] + c);
    }

    cout << max({dp[N][0], dp[N][1], dp[N][2]}) << endl;
}