# Funtour

Nguồn: tham khảo từ bài tập của thầy Đỗ Phan Thuận.

Rating: 2000.

## Đề bài

Khôi rất yêu du lịch. Một ngày Khôi được mẹ cho rất nhiều tiền để bay sang Nhật Bản tham gia các sự kiện về văn hóa Nhật, Khôi vô cùng thích thú. Khôi đã tìm hiểu kĩ thông tin các sự kiện diễn ra, và cậu nhận thấy rằng nếu cậu tham gia được sự kiện $i$ thì sẽ tăng lên độ vui vẻ là $v_i$.

Dịp này ở Nhật Bản có rất nhiều sự kiện được tổ chức, cụ thể có $N$ sự kiện $s_1, s_2, ..., s_N$ ($s_i ∈ [1, K]$) diễn ra theo thứ tự (có nhiều sự kiện có thể lặp lại). Cá nhân Khôi thì lại muốn tham gia các sự kiện theo thứ tự $t_1, t_2, ..., t_M$ ($t_i ∈ [1, K]$), tất nhiên nếu cậu tham gia được sự kiện $t_i$ thì độ vui vẻ của cậu sẽ được cộng thêm $v_{t_i}$.

Tuy nhiên, việc Khôi muốn tham gia các sự kiện theo thứ tự ưa thích dẫn tới việc sẽ có một số sự kiện của Nhật Bản mà Khôi không tham gia được hay là các sự kiện mà Khôi muốn tham gia cũng không tham gia được. Khôi tính ra rằng nếu cậu bỏ qua các sự kiện ưa thích $t_p, t_{p + 1}, ..., t_q$ ($q ≥ p$, $q − p + 1$ sự kiện ưa thích liên tiếp) thì độ vui vẻ của cậu giảm xuống một lượng $−(A + (q − p + 1).B)$. Một điều nữa, nếu như Khôi tham gia hai sự kiện $s_p$ và $s_q$ ($p + 2 ≤ q$) mà không tham gia sự kiện nào giữa hai sự kiện này
thì độ vui vẻ của cậu cũng giảm xuống một lượng $−(A + (q − p + 1)B)$.

#### Yêu cầu:
Tìm độ vui vẻ lớn nhất mà Khôi có thể có được.

## Input:

- Dòng đầu gồm các số nguyên dương $K, N, M, A$ và $B$ theo thứ tự ($K ≤ 1000; n, m ≤ 5000; −100 ≤
A, B ≤ 0$).
- Dòng thứ hai chứa $K$ số nguyên dương $v_1, v_2, ..., v_k$ ($1 ≤ v_i ≤ 100$).
- Dòng thứ ba chứa $N$ số nguyên dương $s_1, s_2, ..., s_N$ ($si ∈ [0, K]$).
- Dòng thứ tư chứa $M$ số nguyên dương $t_1, t_2, ..., t_M$ ($ti ∈ [0, K]$).

## Output

- In ra kết quả bài toán là độ vui vẻ lớn nhất của Khôi.

## Sample

| Input | Output |
| -------- | -------- |
| ||

## Giới hạn

• Subtask $1$ ($10\%$): $K = 1; M ≤ N ≤ 10^3$.
• Subtask $2$ ($15\%$): $K = 1; N < M ≤ 10^3$.
• Subtask $3$ ($15\%$): $A = B = 0$.
• Subtask $4$ ($15\%$): $A = 0$.
• Subtask $5$ ($15\%$): $B = 0$.
• Subtask $6$ ($15\%$): $N, M < 100$.
• Subtask $7$ ($15\%$): Không có giới hạn gì thêm.

## Lời giải:

<details>
<summary>Lời giải</summary>

**1. Subtask 1+ 2 (15%):** K = 1;N, M ≤ 103
Vì chỉ có một sự kiện duy nhất, nên để đạt được độ vui vẻ lớn nhất, Khải chỉ cần tham gia các sự kiện một cách liên tiếp để tối thiểu tổng độ vui vẻ bị giảm.

**2. Subtask 3 (15%):** A = B = 0 Với A = B = 0,
Khải sẽ không bao giờ bị giảm độ vui vẻ trong quá trình tham gia các sự kiện. Vậy nên bài toán trở thành: Tìm các sự kiện Khải nên tham gia để tổng độ vui vẻ nhận được từ các sự kiện là lớn nhất có thể. Gọi dp[i][j] là tổng độ vui vẻ lớn nhất của Khải khi xét tới sự kiện diễn ra thứ i, và sự kiện ưa thích thứ j.
Khi đó: dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]); if (s[i] == t[j])
dp[i][j] = max(dp[i][j], dp[i − 1][j − 1] + vt [j]);
Kết quả là dp[N][M].
Độ phức tạp: O(N ∗ M).

**3. Subtask 4 (15%):** A = 0
Với A = 0, tổng độ giảm vui vẻ sẽ tương ứng với số lượng sự kiện Khải không tham gia và số lượng sự kiện yêu thích mà Khải bỏ qua. Tương tự với Subtask 3, ta vẫn sẽ gọi dp[i][j] với ý nghĩa như cũ. Tuy nhiên, công thức quy hoạch động và quá trình đưa ra kết quả sẽ có sự thay đổi:
dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]) + B;
Với trường hợp S[i] = T[j], ta có lựa chọn tham gia sự kiện (i, j):
dp[i][j] = max(dp[i][j], dp[i − 1][j − 1] + vt[j] );
Kết quả sẽ không phải là dp[N][M], mà ta phải for cố định sự kiện cuối cùng Khải tham gia, để qua đó lấy kết quả tương ứng.
Độ phức tạp: O(N ∗ M).

**4. Subtask 5 (15%):** B = 0
Bây giờ, khi xét đến sự kiện (i, j), ta cần biết liệu sự kiện S[i − 1] và T[j − 1] có được tham gia hay không, để qua đó xác định việc mình có mất đi độ vui vẻ A hay không.
Gọi dp[i][j][0/1][0/1] là tổng độ vui vẻ lớn nhất (không bao gồm độ vui vẻ bị mất do bỏ qua sự kiện S[i] và T[j]) cùng sự kiện được tham gia cuối cùng là (x, y) với x ≤ i và y ≤ j.
Ta có:
- dp[i][j][0][0]: Sự kiện xảy ra thứ i và sự kiện ưa thích thứ j đều không tham gia. (x < i, y < j)
- dp[i][j][0][1]: Sự kiện xảy ra thứ i không tham gia, sự kiện ưa thích thứ j được tham gia.
(x < i, y = j)
- dp[i][j][1][0]: Sự kiện xảy ra thứ i được tham gia, sự kiện ưa thích thứ j không tham gia.
(x = i, y < j)
- dp[i][j][1][1]: Sự kiện xảy ra thứ i và sự kiện ưa thích thứ j đều được tham gia. (x = i, y = j)

Trước hết, ta có công thức quy hoạch động như sau:
- dp[i][j][0][0] = max(dp[i − 1][j][0][0], dp[i][j − 1][0][0]);
- dp[i][j][0][1] = dp[i − 1][j][0][1];
- dp[i][j][1][0] = dp[i][j − 1][1][0];
Nếu S[i] = T[j], ta xét nếu sự kiện S[i] và T[j] là sự kiện đầu tiên được tham gia:
dp[i][j][1][1] = VT[j] if (j = 1)
dp[i][j][1][1] = VT[j]−A if (j > 1) (1) .
Sau đó, xét trường hợp nếu đã có sự kiện được tham gia trước. Khải sẽ mất đi một lượng vui vẻ là A đối với mỗi sự kiện S[i − 1] và T[j − 1] không được tham gia. Công thức quy hoạch động sẽ là:
dp[i][j][1][1] =
dp[i − 1][j − 1][0][0] − 2 ∗ A + VT[j]
dp[i − 1][j − 1][0][1] − A + VT[j]
dp[i − 1][j − 1][1][0] − A + VT[j]
dp[i − 1][j − 1][1][1] + VT[j]
Sau đấy, ta cập nhật các giá trị dp khác:
dp[i][j][0/1][0/1] = max(dp[i][j][0/1][0/1], dp[i][j][1][1])
Tuy nhiên, i và j có thể lên tới 5000, bộ nhớ sẽ không đủ để lưu trữ. Vậy nên ta cần thực hiện tối ưu bộ nhớ. Vì công thức quy hoạch động đối với (i, j) chỉ dựa vào (i − 1, j − 1). Vậy nên, ta chỉ cần sử dụng một mảng kích thước 2 ∗ m ∗ 4 để xử lý.
Kết quả là max(dp[i][j][1][1] − A ∗ (j < m)). Độ phức tạp: O(N ∗ M).

**5. Subtask 6 (15%):** N, M < 100
Sử dụng dp[i][j] với ý nghĩa tương tự Subtask 4. Ta cần xác định sự kiện được tham gia cuối cùng trước sự kiện (i, j) là sự kiện nào. Ta có công thức quy hoạch động như sau:
dp[i][j] = max(dp[k][t]+A∗(k != i)+B∗(i−k)+A∗(t != j)+B∗(j−t));
(k = 1 → i;t = 1 → j)
if (s[i] == t[j])
dp[i][j] = max(dp[i][j], dp[i − 1][j − 1] + vt [j]);
Độ phức tạp: O(M2 ∗ N 2 ).

**6. Subtask 7 (15%):** K ≤ 1000; n, m ≤ 5000; −100 ≤ A, B ≤ 0
Để xử lý Subtask cuối, ta chỉ cần kết hợp hai Subtask 4 và 5. Mọi thứ đều tương tự Subtask 5, trừ trường hợp ta không tham gia vào sự kiện (i, j). Vậy nên, trước tiên ta có: I
- dp[i][j][0][0] = max(dp[i][j − 1][0], dp[i − 1][j][0][0]) + B;
- dp[i][j][0][1] = dp[i − 1][j][0][1] + B;
- dp[i][j][1][0] = dp[i][j − 1][1][0] + B;
Còn lại mọi công thức đều tương tự Subtask 5. Tốc độ thuật toán: O(N ∗ M)

</details>

<details>
<summary>Code (nếu có): </summary>

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 5;;
int n, m, k, i, j, A, B, oo = -1e9, ans;
int a[N], b[N], c[N], d[N][N][2][2];
int f[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> k >> n >> m >> A >> B;
    for (i = 1; i <= k; i++) cin >> a[i];
    for (i = 1; i <= n; i++) cin >> b[i];
    for (i = 1; i <= m; i++) cin >> c[i];
    
    f[1] = A + B;
    for (i = 2; i <= m; i++) 
        f[i] = f[i - 1] + B;
    for (i = 0; i <= n; i++)
    for (j = 0; j <= m; j++)
        d[i][j][0][0] = d[i][j][0][1] = d[i][j][1][0] = d[i][j][1][1] = oo;
    d[0][0][1][1] = 0;
    
    for (i = 0; i <= n; i++)
    for (j = 0; j <= m; j++) {
        if (i > 0) 
            d[i][j][0][0] = max(d[i-1][j][0][0] + B, d[i-1][j][1][0] + A + B);
        if (j > 0) 
            d[i][j][0][0] = max(d[i][j-1][0][0] + B, d[i][j-1][0][1] + A + B);
 
        if (j > 0) 
            d[i][j][1][0] = max(d[i][j-1][1][0] + B, d[i][j-1][1][1] + A + B);
        if (i > 0) 
            d[i][j][0][1] = max(d[i-1][j][0][1] + B, d[i-1][j][1][1] + A + B);
 
        if (b[i] == c[j]) {
          if (i > 0 && j > 0)
              d[i][j][1][1] = a[b[i]] + max(d[i-1][j-1][0][0], max(d[i-1][j-1][0][1], max(d[i-1][j-1][1][0], d[i-1][j-1][1][1])));
          d[i][j][1][1] = max(d[i][j][1][1], a[b[i]] + f[j-1]);
        }
    }
    
    ans = f[m];
    for (i = 1; i <= n; i++) 
        ans = max(ans, max(d[i][m][1][0], d[i][m][1][1]));
    cout << ans;
    
    return 0;
}

</details>