题目链接: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;
}