题解 CF1114D 【Flood Fill】

· · 题解

又是一道小清新 dp 题。

题意简述：有 n 个位置，初始颜色已知。每一次可以将与一个格子相邻的所有颜色相同的格子的颜色更改为任意数。要在尽可能少的步数内将所有格子染成同一个颜色，求这个步数。

思路：

我最开始的思路和原题官方题解的解法 1 比较相似。

首先设计状态，像这种区间进行染色的问题容易想到设 dp_{i,j} 表示将 i\sim j 格子全部染成相同颜色所需的步数。但是这里比较特殊，需要添加一个维度，表示染成最左侧的颜色还是最右侧的颜色。

为什么只考虑左右两种颜色呢？我们的每次合并都在上次的基础上添加了一个数，由于上次的区间是合并好了的，因此除了新添加的数以外，其他的数的颜色均相同。只有这两种颜色，还恰好位于两侧，就只考虑这两种情况即可。

最终设计好的状态：dp_{i,j,bit}，表示 i\sim j 全部染成同一种颜色（bit=0 表示最左侧的颜色，否则是最右侧的颜色）所需的最少步数。

根据这个定义，我们得到初始值：对于 i\ne j，dp_{i,j,0}=dp_{i,j,1}=\inf；否则 dp_{i,j,0}=dp_{i,j,1}=1。

状态的转移：我们枚举当前区间的右端点，从右端点向左枚举左端点，得到当前区间 \left[l,r\right]，使用当前区间向左或向右更新两侧 dp 的值。

设当前颜色为 col（根据 dp 的 bit 值获取左侧或右侧），初始颜色数组为 a_{1,2,\cdots n}，则转移方程为：

\begin{aligned} dp_{i-1,j,0}=&\min(dp_{i-1,j,0},dp_{i,j,bit}+(a_{i-1}\ne col))\\ dp_{i,j+1,1}=&\min(dp_{i,j+1,1},dp_{i,j,bit}+(a_{j+1}\ne col)) \end{aligned}

最终的结果就是 \min(dp_{1,n,0},dp_{1,n,1}) 的值。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, inf = 0x3f3f3f3f;

int n, a[N];
int dp[N][N][2];

void initDP() {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            dp[i][j][0] = dp[i][j][1] = (i == j ? 0 : inf);
        }
    }
}
void updDP(int &a, int b) {a = min(a, b);}

int main() {
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    initDP(); 
    for(int j=1;j<=n;j++) {
        for(int i=j;i>=1;i--) {
            for(int bit=0;bit<=1;bit++) {
                int col = bit ? a[j] : a[i];
                if(i > 1) updDP(dp[i-1][j][0], dp[i][j][bit] + (col != a[i-1]));
                if(j < n) updDP(dp[i][j+1][1], dp[i][j][bit] + (col != a[j+1]));
            }
        }
    }
    printf("%d\n", min(dp[1][n][0], dp[1][n][1]));
    return 0;
}