CF 1114D 区间DP

一道非常基础的区间DP，因为肯定是全部染成里面有的颜色比较快，所以我们只要对每个已经同色的块向外扩张就行了。

转移方程：

dp[i][j]表示i,j区间内都染成同色的最小步骤。

dp[i][j]=min(dp[i][j],dp[i+1][j]+(a[i]!=a[i+1]),dp[i][j-1]+(a[j]!=a[j-1]),dp[i+1][j-1]+2-(a[i]==a[r]));

下附代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int INF=0X3f3f3f3f;
 4 int dp[5005][5005],a[5005],n;
 5 int main(){
 6     memset(dp,INF,sizeof(dp));
 7     scanf("%d",&n);
 8     for (int i=1; i<=n; i++){
 9         scanf("%d",&a[i]);
10         dp[i][i]=0;
11     }
12     for (int len=2; len<=n; len++){
13         for (int l=1; l+len-1<=n; l++){
14             int r=l+len-1;
15             if (a[r]==a[r-1]) dp[l][r]=min(dp[l][r],dp[l][r-1]);
16                 else dp[l][r]=min(dp[l][r],dp[l][r-1]+1);
17             if (a[l]==a[l+1]) dp[l][r]=min(dp[l][r],dp[l+1][r]);
18             else dp[l][r]=min(dp[l][r],dp[l+1][r]+1);
19             if (a[l]==a[r]) dp[l][r]=min(dp[l][r],dp[l+1][r-1]+1);
20         }
21     }
22     printf("%d",dp[1][n]);
23 }

View Code

PS：区间DP掌握的不是很好，这基本上是一个入门题，还被卡了很久，需要多加练习