codeforces1114D.Flood Fill(区间DP)

题目链接:codeforces1114D.Flood Fill

题意:

给n种颜色,每次可以将颜色相同且连续的合并成同一种颜色,问使颜色统一的最少操作次数。

题解:

区间dp。

首先进行离散化,把连续相同颜色的当成一块来处理。dp(i)(j)表示区间[i,j]复原所需要的最少操作次数。

状态转移方程:dp(i)(j)=min(dp(i+1)(j-1),dp(i+1)(j),dp(i)(j-1))+1。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,tot,k;
bool used[5009][5009];
int a[5009],dp[5009][5009];
int solve(int l,int r)
{
    if(used[l][r])
        return dp[l][r];
    used[l][r]=1;
    int &res=dp[l][r];
    if(l==r)
        res=0;
    else
    {
        res=5000;
        if(a[l]==a[r])
            res=min(res,solve(l+1,r-1)+1);
        res=min(res,min(solve(l+1,r),solve(l,r-1))+1);
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        int temp;
        scanf("%d",&temp);
        if(temp==k)
            continue;
        a[++tot]=temp;
        k=temp;
    }
    cout<<solve(1,tot);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。