NOIP集训Day24 DP常见模型3 - 区间

NOIP集训Day24 DP常见模型3 - 区间

A. [CF1572C] Paint

设 \(f_{i, j}\) 表示区间 \([i, j]\) 涂成一种颜色的最小染色次数。可以发现对于区间 \([i, j]\)，一定有一个最优方案使得整个区间最后染色成 \(a_j\)。这是因为 \(j\) 在区间 \([i, j]\) 的边缘，一定存在一个 \(k\in [i, j - 1]\)，使得先将 \([k, j - 1]\) 染成一个个颜色，然后将 \([k, j]\) 统一颜色，再将 \([i, j]\) 统一颜色。如果 \([k, j - 1]\) 按照一种最优方案染完色后与 \(a_j\) 的颜色不同，则要使整个区间颜色相同，只要让 \(j\) 或者 \([k, j - 1]\) 整体变颜色，而无论变成什么颜色，必然使用一次染色，故选择将区间 \([k, j]\) 染成 \(a_j\)，同理，将 \([i, k - 1]\) 和 \([k, j]\) 颜色统一时，都将他们染成 \(a_j\) 也是不劣的。

所以将 \(f_{i, j}\) 重新定义为：将 \([i, j]\) 涂成 \(a_j\) 时的最小染色次数。

则有转移：\(f_{i, j} = \min(f_{i, j - 1} + [a_{j - 1}\ne a_j],\min\limits_{i + 1\le k \le j - 2} (f_{i, k} + f_{k + 1, j} + [a_k \ne a_j]))\)，\(f_{i, i} = 0\)

时间复杂度 \(\Theta(n^3)\)，显然 TLE。

题目中还有一句话：每种颜色最多出现 \(20\) 次。

进一步考虑，对于 \([i, j]\) 中的决策点 \(k\)，总存在一个决策点有 \(a_k = a_j\) 的性质。

证明：将 \([i, j]\) 划分成若干个小区间 \([i, k_1], [k_1 + 1, k_2],\dots,[k_m + 1, j]\)，显然这些区间合并时不需要额外使用一次染色，而若再将其中国的一个区间拆开作为决策点，那么会少一次将左半部分染成 \(a_j\) 的操作，多一次将决策点左右两部分颜色统一的染色操作，所以这样做是不劣的。所以，在枚举 \(k\) 时，只需枚举 \(a_k = a_j\) 的那一部分就好了。

时间复杂度 \(\Theta(20\times n^2)\)。