Subtask 1: ~n \le 5~

• Duyệt tất cả các hoán vị của mảng ~a~ để tìm xem số lần chia đoạn ít nhất thỏa mãn đề bài.

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

Subtask 2: ~n \le 20~

Ta có thể duyệt vét cạn khéo léo hơn, hoặc sử dụng DP bitmask.

Độ phức tạp: ~O~ ~(2^n * n^2)~.

Subtask 3 + Subtask 4: ~n \le 50~

Nhận xét: Ta sẽ chỉ cắt đoạn ở vị trí ~i~ mà ở đó, ~a_i \neq a_{i - 1}~ để đảm bảo số lần cắt là ít nhất. Chính vì vậy, ta sẽ nén mảng (ví dụ, từ {~1, 1, 2, 2, 3, 3~} xuống còn {~1, 2, 3~}) rồi quy hoạch động trên mảng đó.

Giả sử một đoạn ~[l, r]~ là dãy hình nón thỏa mãn, ta sẽ gọi ~a_i~ là "đỉnh nón" khi ~a_i = max(a_l, a_{l+1}, ..., a_r)~

Đầu tiên, ta sẽ nén số mảng ~a~ lại. Gọi ~dp_{a_i, l, r}~ là số lần cắt ít nhất với ~i~ là đỉnh nón trong đoạn từ ~l~ đến ~r~.

-> Với cách tiếp cận này, đáp số bài toán chính là min(~dp_{a_i, i, i + 1}~) với mọi vị trí ~i~ là đỉnh nón trong mảng ~a~.

Vậy, với mọi ~dp_{a_i, l, r}~, ta sẽ làm như sau:

int dp (int mid, int l, int r){
    if (mid == -1) return L[l] + R[r - 1];
    if (f[mid][l][r] != -1) return f[mid][l][r];
    int val = (s[l] == mid);
    if (l && s[l - 1] == mid){
        l--; val++;
    }
    if (r < n && s[r] == mid && l != r){
        val++; r++;
    }
    if (pos[mid].size () == val) return dp (mid - 1, l, r);
    int b = 0;
    if (s[l] != mid) b += L[l];
    if (s[r - 1] != mid) b += R[r - 1];
    int ret = n;
    for (int i : pos[mid]){
        if (i == l || i == r - 1) continue;
        ret = min ({ret, dp (mid - 1, i, r) - L[i] - R[r - 1], dp (mid - 1, l, i + 1) - L[l] - R[i]});
        for (int j : pos[mid]){
            if (j != l && j + 1 != r && j != i) ret = min (ret, dp (mid - 1, i, j + 1) - L[i] - R[j]);
        }
    }
    return f[mid][l][r] = ret + b + base[mid];
} 

với ~s_i~ là phần tử thứ ~i~ của dãy sau khi đã nén, ~n~ là số phần tử của dãy đã nén.

Độ phức tạp: ~O~ ~(n^3)~.