# [Đọc lời giải full ở đây](https://hackmd.io/aRuWX_kZTKGuhmJoROv9Lg)
### Trạng thái quy hoạch động
Đặt `dp[i][j][k]`: giá trị niềm vui lớn nhất đạt được tính đến ngày thứ $i$, người được ghé thăm ở ngày thứ $i$ là $j$ ($0$ là Alice, $1$ là Patchouli) và được ghé thăm liên tiếp $k$ ($1 \leq k \leq 2$) lần.
### Trạng thái cơ sở:
- `dp[0][0][1] = A[0]`: Marisa ghé thăm Alice vào ngày đầu tiên.
- `dp[0][1][1] = B[0]`: Marisa ghé thăm Patchouli vào ngày đầu tiên.
### Công thức chuyển trạng thái:
1. Nếu Marisa ghé thăm Alice vào ngày $i$:
- Nếu Marisa đã thăm Alice vào ngày $i-1$, thì trạng thái sẽ chuyển sang thăm Alice lần thứ 2 liên tiếp:
$$ dp[i][0][2] = \max(dp[i][0][2], dp[i-1][0][1] + A_i) $$
- Nếu Marisa thăm Patchouli vào ngày $i-1$, thì trạng thái sẽ chuyển sang thăm Alice lần đầu tiên:
$$ dp[i][0][1] = \max(dp[i][0][1], \max(dp[i-1][1][1], dp[i-1][1][2]) + A_i) $$
2. Nếu Marisa ghé thăm Patchouli vào ngày $i$:
- Nếu Marisa đã thăm Patchouli vào ngày $i-1$, thì trạng thái sẽ chuyển sang thăm Patchouli lần thứ 2 liên tiếp:
$$ dp[i][1][2] = \max(dp[i][1][2], dp[i-1][1][1] + B_i) $$
- Nếu Marisa thăm Alice vào ngày $i-1$, thì trạng thái sẽ chuyển sang thăm Patchouli lần đầu tiên:
$$ dp[i][1][1] = \max(dp[i][1][1], \max(dp[i-1][0][1], dp[i-1][0][2]) + B_i) $$
### Kết quả:
- Giá trị lớn nhất của niềm vui ở ngày cuối cùng sẽ là:
$$ \max(dp[n-1][0][1], dp[n-1][0][2], dp[n-1][1][1], dp[n-1][1][2]) $$
## Định nghĩa:
$\texttt{dp[i][j][k]}$ : Niềm vui lớn nhất khi xét đến ngày thứ $i$ với người bạn cuối cùng là $j$ và đã thăm người bạn $j$ được $k$ ngày.
Trong mảng quy hoạch động này, chiều $j$ sẽ chỉ mang 2 giá trị $\texttt{0}$ hoặc $\texttt{1}$ với ý nghĩa sau:
- $\texttt{0}$: thăm Alice.
- $\texttt{1}$: thăm Patchouli.
## Khởi tạo và trường hợp cơ sở:
Khởi tạo mảng $\texttt{dp} = - \infty$.
Trường hợp cơ sở:
- $\texttt{dp[1][0][1]} = A_1$: Thăm Alice vào ngày đầu tiên.
- $\texttt{dp[1][1][1]} = B_1$: Thăm Patchouli vào ngày đầu tiên.
## Chuyển trạng thái:
Xét từ ngày thứ 2 trở đi:
### Thăm Alice(j = 0):
1. Thăm Alice 1 ngày liên tiếp(k = 1): Trước đó vào ngày thứ $i-1$ buộc phải thăm Patchouli trong 1 hoặc 2 ngày liên tiếp: $$\texttt{dp[i][0][1]} = \max(\texttt{dp[i-1][1][1]}+A_i,\texttt{dp[i-1][1][2]}+A_i)$$
2. Thăm Alice 2 ngày liên tiếp(k = 2): Trước đó vào ngày thứ $i-1$ buộc phải thăm Alice trong 1 ngày liên tiếp: $$\texttt{dp[i][0][2]} = \texttt{dp[i-1][0][1]}+A_i$$
### Thăm Patchouli(j = 1):
1. Thăm Patchouli 1 ngày liên tiếp(k = 1): Trước đó vào ngày thứ $i-1$ buộc phải thăm Alice trong 1 hoặc 2 ngày liên tiếp: $$\texttt{dp[i][1][1]} = \max(\texttt{dp[i-1][0][1]}+B_i,\texttt{dp[i-1][0][2]}+B_i)$$
2. Thăm Patchouli 2 ngày liên tiếp(k = 2): Trước đó vào ngày thứ $i-1$ buộc phải thăm Patchouli trong 1 ngày liên tiếp: $$\texttt{dp[i][1][2]} = \texttt{dp[i-1][1][1]}+B_i$$
## Đáp án
Sau khi tính toán đến ngày thứ $n$, đáp án là giá trị lớn nhất trong tất cả các trạng thái có thể có ở ngày cuối cùng: $$\max(\texttt{dp[n][0][1]},\texttt{dp[n][0][2]},\texttt{dp[n][1][1]},\texttt{dp[n][1][2])}$$
hoangbach2022
Created at
32 likes