【CF-1114D】Flood Fill 区间DP

Flood Fill

题意

有n个方块，每个方块都有一个颜色，现在玩一个游戏，开始时选择一个方块作为起点，

接下来每个回合都可以把起始点所在连通块变成任意一个颜色，问最少需要多少次，使

得所有方块颜色相同？

题解

对于区间([l,r])最后肯定是变成(l)或者(r)的颜色，

(dp[l][r][0/1])分别表示区间([l,r])变为(l/r)的颜色所需的最少操作步骤。

(dp[l][r][0])从(dp[l+1][r][0/1])转移，不从(dp[l][r-1][0/1])转移

因为每次选择的都是起始点坐在的连通块，如果转移：区间([l,r-1])要先

变成(r)的颜色，然后再变成(l)的颜色，这样就相当于是从(dp[l+1][r][1])转移的。

(dp[l][r][1])同理：从(dp[l][r-1][0/1])转移。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
const int inf=0x3f3f3f3f;
typedef long long ll;

int dp[N][N][2],arr[N];
int main()
{
    int n;
    scanf("%d",&n);
    memset(dp,0x3f,sizeof(dp));
    for(int i=1; i<=n; ++i)
    {
        scanf("%d",&arr[i]);
        dp[i][i][0]=dp[i][i][1]=0;
    }
    for(int len=2; len<=n; len++)
    {
        for(int l=1; len+l-1<=n; l++)
        {
            int r=len+l-1;
            dp[l][r][0]=min(dp[l+1][r][0]+(arr[l+1]!=arr[l]),dp[l+1][r][1]+(arr[r]!=arr[l]));
            dp[l][r][1]=min(dp[l][r-1][0]+(arr[l]!=arr[r]),dp[l][r-1][1]+(arr[r-1]!=arr[r]));
        }
    }
    printf("%d
",min(dp[1][n][0],dp[1][n][1]));
    return 0;
}
/*
*/