CF1114D 【Flood Fill】

佚名 6年前 (2019-04-18) 随笔 574人围观抢沙发百度已收录

Solution

一看就是很水的区间DP

\(dp[i][j]\)表示区间\([l,r]\)都涂成同色的代价。
\(dp[i][j] = min( dp[i][j], dp[i][k] + dp[k][j] + 1)\)

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<bits/stdc++.h>
using namespace std;
int n, x, a[5010], f[5010][5010], y, cnt;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &x);
        if (x != y) a[++ cnt] = x;
        y = x;
    }
    for (int i = 1; i <= cnt; i ++)
        for (int j = 1; j + i <= cnt; j ++)
            if (a[j] == a[j + i])
                f[j][j + i] = f[j + 1][j + i - 1] + 1;
            else f[j][j + i] = std::min(f[j + 1][j + i], f[j][j + i - 1]) + 1;
    return printf("%d\n", f[1][cnt]), 0;
}