VOJ - CUTSEG

Source: CUTSEG
Tags: Dynamic Programming

Problem:
Cho một dãy N chữ số thuộc đoạn 0..9. Ở mỗi bước ta có thể lấy ra từ dãy một đoạn liên tiếp các chữ số giống nhau và nhận được một số tiền bằng bình phương độ dài đoạn được lấy ra. Nếu sau khi lấy, dãy đã cho bị tách ra thành 2 dãy con, 2 dãy con này lập tức được sát nhập lại thành 1 (giữ nguyên thứ tự). Tính lượng tiền lớn nhất thu được.
N ≤ 200.

Ví dụ:
Input:
6
100011

Output:
18

Explanation:
Lấy đoạn từ 2 đến 4 trước và có được số tiền là 9. Sau đó lấy tiếp tất cả và nhận thêm số tiền là 9. Tổng cộng là 18.

Solution:
Nếu có một đoạn liên tiếp những số giống nhau chắc chắn một lần ta phải lấy hết đoạn đó, tại vì lấy từng khúc nhỏ thì sẽ không nhiều tiền. Vì vậy ta nén dãy số lại, tức là những đoạn có nhiều số liên tiếp giống nhau ta sẽ thay thế bằng một phần tử thôi, và thêm một mảng để lưu số lượng.
Gọi DP[L][R][K] là cách xử lý đoạn L → R có K phần tử bằng phần tử R theo sau.
Ví dụ bạn có dãy sau:
1112211133411551
bạn lấy đi các đoạn 334 và 55 thì sẽ được dãy mới sau:
11122111  11  1
Như vậy lúc này bạn cần xử lý đoạn 11122111 với 3 phần tử bằng phần tử R theo sau.
Gọi A[i] là giá trị của phần tử thứ i và C[i] là số lượng phần tử ban đầu sau khi bị nén ở vị trí i.
Ta có:
Nếu L = R thì DP[L][R][K] = (C[R] + K) ^ 2. Do lúc này chỉ xử lý 1 phần tử, ta chỉ có một cách duy nhất là lấy nó đi cùng K thằng theo sau nó.
Nếu L < R, ta có 2 cách để xử lý:
- Cách 1: Lấy luôn phần tử R cùng K thằng theo sau nó, ta có công thức cho cách này là
DP[L][R][K] = DP[L][R - 1][0] + DP[R][R][K], tức là, ta sẽ xử lý đoạn L → R - 1 với không có thằng nào theo sau hết, vì đã xử lý hết đằng sau rồi, ta lấy luôn phần tử R cùng K thằng theo sau do đó chỉ cần xử lý riêng một phần tử R cùng K thằng theo sau.
- Cách 2: Kéo phần tử R cùng K thằng theo sau đi theo một phần tử X nào đó nằm giữa [L, R) mà A[X] = A[R], công thức cho cách này là:
DP[L][R][K] = min(DP[L][X][C[R] + L] + DP[X + 1][R - 1][0]) với mọi X trong [L, R), tức là, ta cần lấy đi đoạn ở giữa X và R trước để có thể nối C[R] + K phần tử theo sau X, do đó ta cần lấy đi đoạn đó mà không có phần tử nào theo sau, lúc này bài toán trở thành xử lý đoạn L → X với C[R] + K thằng theo sau đoạn đó.
Lấy min 2 cách sẽ ra được đáp án cuối cùng.
Độ phức tạp O(N ^ 3).

Code:
#include <iostream>
#include <string.h>

using namespace std;

int n, a[215], c[215], dp[215][215][215];
string s;

int solve(int l, int r, int k) {
    if (dp[l][r][k] == -1) {
        if (l == r) dp[l][r][k] = (c[r] + k) * (c[r] + k);
        else {
            dp[l][r][k] = solve(l, r - 1, 0) + solve(r, r, k);
            for (int i = l; i < r; ++i)
                if (a[i] == a[r])
                    dp[l][r][k] = max(dp[l][r][k], solve(l, i, c[r] + k) + solve(i + 1, r - 1, 0));
        }
    }
    return dp[l][r][k];
}

int main() {
    cin >> n >> s;
    n = 0;
    for (int i = 0; i < s.length(); ++i)
        if (n == 0 || s[i] - 48 != a[n])
            a[++n] = s[i] - 48, c[n] = 1;
        else ++c[n];
    memset(dp, -1, sizeof dp);
    cout << solve(1, n, 0);

}