\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <Cày trâu>}}\)

• Để cho gọn, ta sẽ chọn như sau

\(cur = 0\) là chọn đi biển và thu về \(a_i\)

\(cur = 1\) là chọn đi bắt sâu bọ trên núi và thu về \(b_i\)

\(cur = 2\) là chọn làm bài tập về nhà và thu về \(c_i\)

\(cur = 3\) là không chọn gì và không thu về gì (thu về \(0\))

• \(\color{#903030}{\text{<Cày siêu trâu>}}\) Sinh dãy tứ phân độ dài \(n\) và kiêm tra rồi tính toán từng dãy

Với mỗi dãy mình sẽ kiểm tra xem có 3 phần tử kề nhau cùng có giá trị \(\in \{0, 1, 2\}\) hay không

Nếu không thì tính toán độ hạnh phúc của nó. Và trong những dãy thế mình chọn độ hạnh phúc lớn nhất

Mỗi số có 4 cách chọn, nên tổng số cách chọn là \(4^n\) \(\rightarrow\) độ phức tạp \(\Theta(4 ^ n)\)

• \(\color{#903030}{\text{<Cày trâu>}}\) Sinh dãy tam phân độ dài \(n\) và kiêm tra rồi tính toán từng dãy

Vì các giá trị \(a_i, b_i, c_i\) không âm, nên thay vì không chọn gì giữa 2 số ở \(i - 2\) và \(i\) thì luôn chọn được số thứ 3 khác 2 số còn lại mà nhận kết quả cao hơn là không chọn gì

Với mội dãy mình sẽ kiểm tra xem có 2 phần tử nào kề nhau bằng nhau không.

Nếu không thì tính toán độ hạnh phúc của nó. Và trong những dãy thế mình chọn độ hạnh phúc lớn nhất

Mỗi số có 3 cách chọn, nên tổng số cách chọn là \(3^n\) \(\rightarrow\) độ phức tạp \(\Theta(3 ^ n)\)

• \(\color{#903030}{\text{<Nhánh cận>}}\) Sinh dãy tam phân độ dài \(n\) sao cho 2 phần tử kề nhau khác nhau và tính toán từng dãy

Goi \(pre\) là số bị chọn lúc trước, khởi tạo là \(4\) sau đó thì các khả năng là \(pre \in \{0, 1, 2\}\)

Sau đó mình chọn các số trong \(cur \in \{0, 1, 2\}\) thỏa \(cur \neq pre\) và chọn \(cur\) vào dãy đang xét

Số đầu có \(3\) cách chọn, \(n - 1\) số còn lại có 2 cách chọn, tổng cách chọn là \(3 \times 2^(n - 1) \approx 2^(n + 0.5)\) \(\rightarrow\) độ phức tạp \(\Theta(2 ^ n)\)

\(\color{#300000}{\text{Hint 2 <Quy hoạch động>}}\)

• \(\color{#903030}{\text{<Đệ quy có nhớ>}}\) Gọi \(magic(pos, pre)\) là kết quả tối ưu của đoạn \([pos, n]\) với lần chọn trước là \(pre\)

• Với \(pos = 1\) thì có 3 cách chọn \(magic(2, 0), magic(2, 1), magic(2, 2)\) và thu được các giá trị \(a_1, b_1, c_1\)

Ta có \(magic(1, 4) = max\{magic(2, 0) + a_1, magic(2, 1) + b_i, magic(2, 2) + c_1\}\)

• Với \(pos > 1\) ta chọn được 2 số \(cur_1, cur_2\) thỏa \(\{pre, cur_1, cur_2\} = \{0, 1, 2\}\)

Gọi \(val_1, val_2\) là giá trị nhận được khi chọn \(cur_1, cur_2\)

Ta có \(magic(pos, pre) = max(magic(pos + 1, cur_1) + val_1, magic(pos + 1, cur_2) + val_2)\)

• Kết quả bài toán \(magic(1, 4)\) hoặc bất cứ \(magic(1, pre \notin \{0, 1, 2\})\) nào

• Và ta chỉ cần thêm nhớ vào khi \([pos, pre]\) đã được tính

Có tất cả \(O(n)\) khả năng cho \(pos\) và \(O(3)\) khả năng cho \(pre\). Nên độ phức tạp bộ nhớ \(O(f(x)) = O(3 \times n)\)

Có chi phí chuyển \(O(g(x)) = O(2)\) cho cách chọn \(cur_1\) hoặc \(cur_2\). Nên độ phức tạp thời gian là \(O(f(x) \times g(x)) = O(6 \times n)\)

• \(\color{#903030}{\text{<Quy hoạch động>}}\) Gọi \(f[pos][cur]\) là kết quả tối ưu của đoạn \([1, pos]\) với lần chọn này là \(cur\)

• Với \(pos = 1\), ta chỉ việc chọn giá trị ứng với \(cur\)

Có \(f[1][0] = a_1, f[1][1] = b_1, f[1][2] = c_1\)

• Khi \(pos > 1\), ta chọn được 2 số \(pre_1, pre_2\) thỏa \(\{pre_1, pre_2, cur\} = \{0, 1, 2\}\)

Gọi \(val_1, val_2\) là giá trị nhận được khi chọn \(pre_1, pre_2\)

Ta có \(f[pos][cur] = max(f[pos - 1][pre_1] + val_1, f[pos - 1][pre_2] + val_2)\)

• Kết quả bài toán là \(max\{f[n][0], f[n][1], f[n][2]\}\)

• Phân tích độ phức tạp:

Có tất cả \(O(n)\) khả năng cho \(pos\) và \(O(3)\) khả năng cho \(cur\). Nên độ phức tạp bộ nhớ \(O(f(x)) = O(3 \times n)\)

Có chi phí chuyển \(O(g(x)) = O(2)\) cho cách chọn \(pre_1\) hoặc \(pre_2\). Nên độ phức tạp thời gian là \(O(f(x) \times g(x)) = O(6 \times n)\)

\(\color{#009933}{\text{Preference Accepted Code }}\): Quy hoạch động

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    int n;
    cin >> n;

    int a[n + 1], b[n + 1], c[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> a[i] >> b[i] >> c[i];

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

    cout << max({dp[n][0], dp[n][1], dp[n][2]});
    return 0;
}```

---
## $\color{#300000}{\text{Hint 3 <Tối ưu bộ nhớ>}}$


- Nhận thấy $f[i][0 \dots 2]$ sẽ chỉ bị ảnh hưởng bởi $f[i - 1][0 \dots 2]$.

> Nên ta sẽ dùng biến $cur_x = f[i][x]$ và $pre_x = f[i - 1][x]$

> Tại mỗi $i$ tiếp theo, ta gán lại $pre = cur$ vì lúc này $pre$ là của vị trí $i - 1$


- Nhận thấy tại mỗi vị trí $i$ mình có thể nhận cặp 3 phần tử $a_i$, $b_i$, $c_i$ và giải tiếp

> Nên ta không cần lưu 3 mảng $a[], b[], c[]$ mà có thể nhận vào rồi tính toán ngay luôn

---
# $\color{#009933}{\text{Preference Accepted Code }}$: Giải trực tiếp, Quy hoạch động
# $^{^{\color{#7f5f3f}{\text{Complexity : }} O(n)\ \color{#7f5f3f}{\text{time}}\ ||\ O(1)\ \color{#7f5f3f}{\text{memory}}}}$
```cpp

int main()
{
    int n;
    cin >> n;

    int pre0, pre1, pre2;
    int cur0, cur1, cur2;
    pre0 = pre1 = pre2 = 0;
    cur0 = cur1 = cur2 = 0;
    for (int i = 0; i < n; ++i)
    {
        int a0, a1, a2;
        cin >> a0 >> a1 >> a2;

        cur0 = max(pre1, pre2) + a0;
        cur1 = max(pre0, pre2) + a1;
        cur2 = max(pre0, pre1) + a2;

        pre0 = cur0;
        pre1 = cur1;
        pre2 = cur2;
    }

    cout << max({cur0, cur1, cur2});
    return 0;
}