题解 CF1114D 【Flood Fill】

· · 题解

每日一唠：

这道题难度良心真的评的有点高

是一个区间DP并没有什么很难想的地方

我是在做完她之后学长推荐才过来的

建议大家也做一下可能泥萌早就做完了

正文：

区间DP正常思路即可

然后开数组一定要看数据范围！

为什么？这还用问吗？我MLE一气之下就变成了RE

    for (int i = 1; i <= n; i++) {
        int x;
        scanf ("%d", &x);
        if (x != fre) a[++num] = x;
        fre = x;
    }

这一个地方我是借鉴了一下别人题解的思路Orz， 处理的很巧妙， 在输入的同时就把重复的颜色相同但是长短不一的连通块全都处理成一块， 因为他们颜色都一样所以这样处理完全没问题啊

然后dp

    for (int l = 1; l <= num; l++)
        for (int i = 1; i + l <= num; i++) 
            int j = i + l;

第一层循环枚举区间长度， 第二层循环枚举可行的左区间， j是算出的右区间， 注意不同题目不同分析，有的题目必须给f赋一个很大的初值再更新之类的，而此题可以不用这样。

            if (a[i] == a[j]) f[i][j] = f[i + 1][j - 1] + 1;
            else f[i][j] = min (f[i + 1][j], f[i][j - 1]) + 1;

分两种情况的dp

1.两边的颜色相同那就是中间的长度再加上1（因为是合并）

2.两边颜色不同那就在两边分别取最小即可 。

The Last：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 10101;
int num, n, a[N], fre, f[N][N];
int main () {
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf ("%d", &x);
        if (x != fre) a[++num] = x;
        fre = x;
    }
    for (int l = 1; l <= num; l++)
        for (int i = 1; i + l <= num; i++) {
            int j = i + l;
            if (a[i] == a[j]) f[i][j] = f[i + 1][j - 1] + 1;
            else f[i][j] = min (f[i + 1][j], f[i][j - 1]) + 1;
        }
    printf ("%d\n", f[1][num]);
    return 0;
}

谢谢收看， 祝身体健康！