[CF1114D] Flood Fill - 区间dp

Description

$ n $ 个方块排成一排，第 $ i $ 个颜色为 $ c_i $。定义一个颜色联通块 $ [l,r] $ 当且仅当 $ l $ 和 $ r $ 之间所有方块的颜色相同。现在你可以选定一个起始位置 $ p $，每次将 $ p $ 所在颜色联通块的所有方块颜色改成另一种。这个操作可能将多个颜色联通块合并成一个。问最少要多少步，能让 $ [1,n] $ 变成一个颜色联通块。
$ 1\le n,c_i\le 5000 $

Solution

先把序列 unique 一下，使得相邻两个位置颜色总不同，然后区间 DP

考察 \(c[i]\) 与 \(c[j]\) 是否相等，如果相等则 \(f[i][j]\) 的转移来源为 \(f[i+1][j-1]\)，否则转移来源在 \(f[i+1][j],f[i][j-1]\) 中选取

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 5005;

int n,a[N],f[N][N];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    n=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=n;i++) f[i][i]=0;
    for(int l=2;l<=n;l++) {
        for(int i=1;i+l-1<=n;i++) {
            int j=i+l-1;
            if(a[i]==a[j]) f[i][j]=f[i+1][j-1]+1;
            else f[i][j]=min(f[i][j-1]+1,f[i+1][j]+1);
        }
    }
    cout<<f[1][n];
}

[CF1114D] Flood Fill - 区间dp

原文：https://www.cnblogs.com/mollnn/p/12944161.html