专栏文章

洛谷 P5189 题解

llzy20091001
P5189题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miosu7xi
此快照首次捕获于
2025/12/03 00:35
3 个月前
此快照最后确认于
2025/12/03 00:35
3 个月前
查看原文
洛谷 P5189 [COCI 2009/2010 #5] ZUMA
思路来自 LiaoYF大佬的题解，当时花了不少功夫才读懂，这里写一篇更易懂、明了的题解。

题意简述

有一个长度的数列 c1,2,⋯ ,nc_{1, 2, \cdots, n}。你可以进行 2 种操作：
  • 在其中任意位置添加任意一个数；
  • 删除任意一段满足以下条件的区间 cl,⋯ ,rc_{l, \cdots ,r}：
    • r−l+1≥kr - l + 1 \ge k；
    • cl=cl+1=⋯=crc_l = c_{l + 1} = \cdots = c_r。
添加操作代价为 11，删除操作代价为 00。求使得整个数列都被删去的最小代价。

思路

考虑区间 DP。

状态

套路的做法是设删除区间 [l,r][l, r] 的代价为 f(l,r)f(l, r)。但是我们可以通过删除中间部分，把两个原本不相邻的区间拼成一个新的大区间。这启示我们构造的状态应当包含 [l,r][l, r] 以外的信息。
具体地，设 f(l,r,x)f(l, r, x) 表示：在“删除了 [r+1,n][r + 1, n] 内所有不等于 crc_r 的数”的前提下，“将 [l,r][l, r] 和 rr 后面的前 xx 个数共同删去”的代价。（这 xx 个数都是原有而非我们添加的，前提中也删除了所有我们添加的数。）
这个定义非常拗口。为什么要这么定义？因为这就相当于“删除了中间部分”，把 crc_r 和后面所有能一起删去的数拼在了一起。

转移

转移有两种：
  • 直接删除 crc_r 和后面的 xx 个数：如果 x+1<kx + 1 < k，那么我们就要添加 k−x−1k - x - 1 个数。所以这种转移的方程为 f(l,r,x)=f(l,r−1,0)+max⁡{0,k−x−1}f(l, r, x) = f(l, r - 1, 0) + \max \{ 0, k - x - 1 \}（为什么 f(l,r−1,0)f(l, r - 1, 0) 第三个参数是 00？牢记我们状态定义的前提就是已经把 rr 以后所有不等于 crc_r 的数都删去了）；
  • 若存在 i∈[l,r]i \in [l, r] 且 ci=crc_i = c_r，那么我们也可以先删去 [i+1,r−1][i + 1, r - 1]，然后再把 ci,crc_i, c_r 以及后面的 xx 个数一起删除。这种转移的方程为 f(l,r,x)=f(i+1,r−1,0)+f(l,i,x+1)f(l, r, x) = f(i + 1, r - 1, 0) + f(l, i, x + 1)。
枚举所有转移取最小即可。

小优化

删除操作没有代价，因此长度大于等于 kk 且可以被删除的区间没有意义，第三维的取值范围可以设为 [0,k−1][0, k - 1]。当然，转移方程也随之有一点小变化。

边界

l=rl = r 时 f(l,r,x)=0f(l, r, x) = 0。

复杂度分析

时间复杂度为 O⁡(N3K)\operatorname{O}(N^3K)，但常数很小；空间复杂度为 O⁡(N2K)\operatorname{O}(N^2K)。

实现

CPP
#include <iostream>

using namespace std;

const int N = 100, K = 5;

int c[N + 5], f[N + 5][N + 5][K + 5];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, k;

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> c[i];

    for (int len = 1; len <= n; len++)
        for (int l = 1, r = l + len - 1; r <= n; l++, r++)
            for (int x = 0; x < k; x++)
            {
                f[l][r][x] = f[l][r - 1][0] + k - x - 1;
                for (int i = l; i < r; i++)
                    if (c[i] == c[r])
                        f[l][r][x] = min(f[l][r][x], f[l][i][min(x + 1, k - 1)] + f[i + 1][r - 1][0]);
            }

    cout << f[1][n][0] << "\n";

    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...