染色

· · 题解

\mathcal O(n^3)

设 f_{i,j} 为在 i 这个点，前面最近的与 i 颜色不相同的位置为 j 的答案。

转移：枚举 j 前面的一个点 k，然后进行转移。

f_{i,j}=\max\limits_{k=0}^{j-1}f_{j,k}+[a_{j+1}=a_k]\times a_k+\text{calc}(j+1,i)

根据定义，k 位置与 j+1 位置颜色相同，所以需要计算 [a_{j+1}=a_k]\times a_k。j+1\sim i 为同一种颜色，所以 \text{calc}(j+1,i) 可以预处理前缀和 \mathcal O(1) 查询。

具体地，令 s_i=s_{i-1}+[a_i=a_{i-1}]\times a_i，则 \text{calc}(j+1,i)=s_i-s_{j+1}。

此做法时间复杂度 \mathcal O(n^3)，空间复杂度 \mathcal O(n^2)。期望得分 35 分。

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
            f[i][j] = 0;
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + (a[i] == a[i - 1]) * a[i];
    LL ans = 0;
    for (int i = 1; i <= n; ++i) {
        f[i][0] = s[i];
        for (int j = 1; j < i; ++j) {
            for (int k = 0; k < j; ++k)
                f[i][j] = max (f[i][j], f[j][k] + s[i] - s[j + 1] + (a[j + 1] == a[k]) * a[k]);
        }
    }
    for (int i = 0; i <= n; i++)
        ans = max (ans, f[n][i]);
    cout << ans << '\n';
}

\mathcal O(n^2) solution 1

观察以下转移：

for (int k = 0; k < j; ++k)
    f[i][j] = max (f[i][j], f[j][k] + s[i] - s[j + 1] + (a[j + 1] == a[k]) * a[k]);

发现 f_{j,k}-s_{j+1}+[a_{j+1}=a_k]\times a_k 与 i 并没有关系。

考虑提出 s_i，令 g_i 表示 \max\limits_{k=0}^{i-1}f_{i,k}-s_{i+1}+[a_{i+1}=a_k]\times a_k。

我们得到新的转移：f_{i,j}=g_j+s_i。

此做法时间复杂度 \mathcal O(n^2)，空间复杂度 O(n^2)。期望得分 50 分。

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
            f[i][j] = 0, g[i] = 0;
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + (a[i] == a[i - 1]) * a[i];
    LL ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            f[i][j] = g[j] + s[i];
        }
        for (int k = 0; k < i; ++k)
            g[i] = max (g[i], f[i][k] - s[i + 1] + (a[i + 1] == a[k]) * a[k]);
    }
    for (int i = 0; i <= n; i++)
        ans = max (ans, f[n][i]);
    cout << ans << '\n';
}

\mathcal O(n^2) solution 2

考虑优化空间。

观察上面的代码，发现其中出现的 f_{i,j} 与 f_{i,k} 并无本质区别。

考虑将原来的 f_{i,k} 替换为 g_k+s_i。

设 f_{i}=\max\limits_{j=0}^{i-1}g_j+s_i。这样答案就为 f_n。

此做法时间复杂度 \mathcal O(n^2)，空间复杂度 \mathcal O(n)。期望得分 50 分。

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i <= n; ++i) f[i] = 0, g[i] = 0;
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + (a[i] == a[i - 1]) * a[i];
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) f[i] = max (f[i], g[j] + s[i]);
        for (int k = 0; k < i; ++k) g[i] = max (g[i], g[k] + s[i] - s[i + 1] + (a[i + 1] == a[k]) * a[k]);
    }
    cout << f[n] << '\n';
}

\mathcal O(n)

看这个式子：f_{i}=\max\limits_{j=0}^{i-1}g_j+s_i。

将 s_i 提出来，令 \text{mx}_{i}=\max\limits_{j=0}^{i-1}g_j。这样 f_i=\text{mx}_{i-1}+s_i。

上面提到 g_i=\max\limits_{k=0}^{i-1}g_k+s_i-s_{i+1}+[a_{i+1}=a_k]\times a_k。

将 s_i-s_{i+1} 提出来，这样能转移的 k 分为 a_{k}=a_{i+1} 和 a_{k}\neq a_{i+1} 两种。

然后就做完了。

此做法时间复杂度 \mathcal O(n)，空间复杂度 \mathcal O(n)。期望得分 100 分。

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i <= n; ++i) f[i] = g[i] = mx[i] = 0, t[a[i]] = 0;
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + (a[i] == a[i - 1]) * a[i];
    for (int i = 1; i <= n; ++i) {
        f[i] = mx[i - 1] + s[i];
        g[i] = max (mx[i - 1], t[a[i + 1]]) + s[i] - s[i + 1];
        t[a[i]] = max (t[a[i]], g[i] + a[i]);
        mx[i] = max (mx[i - 1], g[i]);
    }
    cout << f[n] << '\n';
}