【Codeforces Round #538 (Div. 2) D. Flood Fill】区间DP

D. Flood Fill

题意

给你一个颜色序列，每个位置有一个颜色，选择一个起始位置，每次可以改变包含这个位置的颜色段，将这个颜色段修改为任意一个颜色， 问最少操作多少次。

$1\le n\le 5000$
做法

由于要求每次操作都要包含起始段，所以每次操作都应该是连续的，也就是如果我们现在改变$(l,r)，那么(l,r?1),(l+1,r),(l+1,r?1)$一定已经改变完成，所以直接$dp$即可，$dp[l][r]$表示将l-r这个区间变为同一种颜色的最小代价。
当l的颜色与r的颜色相同:$dp[l][r]=dp[l+1][r?1]+1$
当l的颜色与r的颜色不同:$dp[l][r]=min(dp[l+1][r],dp[l][r?1])+1$

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 5005;
const int INF = 0x3f3f3f3f;
int dp[maxn][maxn];
int a[maxn];
int b[maxn];
int dfs(int l,int r)
{
    if(dp[l][r]!=INF) return dp[l][r];if(l==r) dp[l][r]=0;else if(l+1==r) dp[l][r]=1;else if(b[l]==b[r]) dp[l][r]=dfs(l+1,r-1)+1;else dp[l][r]=min(dfs(l,r-1),dfs(l+1,r))+1;return dp[l][r];
}
int main()
{
    int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);memset(dp,INF,sizeof(dp));int cnt=0;for(int i=1;i<=n;i++) if(a[i]!=a[i-1]) b[++cnt]=a[i];printf("%d\n",dfs(1,cnt));return 0;
}