Gọi ~dp_{i,j}~ là tổng số chiều cao của bạn nam phân biệt trong các bức ảnh tốt nhất đến bạn thứ ~i~ khi chụp ~j~ bức ảnh Ta có:

• ~dp_{i, j}~ = ~dp_{i, k} + cost(k+1, i)~ ( ~1 \le k < i~ ), với ~cost (k+1, i)~ và số chiều cao phân biệt từ bạn ~k+1~ đến bạn thứ ~i~.

Với ~N \le 50~

Ta tính ~cost(i, j)~ bằng CTDL set, map trong ~\mathcal {O}(N*\log(N))~

int cost(int l, int r){
    set<int> sets;
    FOR (i, l, r) sets.insert(a[i]);
    return sets.size();
}

void solve(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    for (int j = 1; j <= n; j++){
        for (int i = j; i <= n; i++){
            for (int l = i-1; l >= 0; l--){
                maximize(dp[i][j], dp[l][j-1] + cost(l+1, i));
            }
        }
        maximize(ans, dp[n][j]);
    }
    cout << ans;
}

Độ phức tạp : ~\mathcal {O}(N^{3} * K * \log(N))~

Với ~ N \le 200 ~

Ta tính ~cost(i, j)~ bằng cách duy trì 2 con trỏ sử dụng CTDL multiset, map với trong ~\mathcal {O}(\log(N))~

int n, k, dp[255][255], a[255];
int L, R;
multiset<int> ms;
set<int> sets;
int COST;

int cost(int l, int r){
    while (L > l){
        ms.insert(a[--L]);
        if (ms.count(a[L]) == 1) COST++;
    }
    while (L < l){
        if (ms.count(a[L]) == 1) COST--;
        ms.erase(ms.find(a[L++]));
    }
    while (R > r){
        if (ms.count(a[R]) == 1) COST--;
        ms.erase(ms.find(a[R--]));
    }
    while (R < r) {
        ms.insert(a[++R]);
        if (ms.count(a[R]) == 1) COST++;
    }
    return COST;
}

Đô phức tạp ~\mathcal {O}(N^{2}*K*\log(N))~

Ta có thể nén mảng sử dụng mảng ~cnt~ thay cho multiset giảm độ phứt tạp xuống còn ~\mathcal {O}(N^{2}*K)~