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\ast 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\ne 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 $d{p}_{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($d{p}_{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 $d{p}_{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)$.