最简单的那类区间dp，昨天晚上心态不对，不知道在打什么。。
/* dp[l][r]表示区间[l,r]都涂成同色的代价 dp[l][r]可以由dp[l][r-1],dp[l+1][r],dp[l+1][r-1]转移得到 */ #include<bits/stdc++.h> using namespace std; #define maxn 5005 int dp[maxn][maxn]; int n,color[maxn]; int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>color[i]; memset(dp,0x3f,sizeof dp); for(int i=1;i<=n;i++)dp[i][i]=0; for(int len=2;len<=n;len++) for(int l=1;l+len-1<=n;l++){ int r=l+len-1; if(color[l]==color[l+1])dp[l][r]=min(dp[l][r],dp[l+1][r]); else dp[l][r]=min(dp[l][r],dp[l+1][r]+1);//向左端点扩展的情况 if(color[r]==color[r-1])dp[l][r]=min(dp[l][r],dp[l][r-1]); else dp[l][r]=min(dp[l][r],dp[l][r-1]+1);//向右端点扩展的情况 if(color[r]==color[l])dp[l][r]=min(dp[l][r],dp[l+1][r-1]+1);//两侧扩展的情况 } printf("%d\n",dp[1][n]); }
转载于:https://www.cnblogs.com/zsben991126/p/10361410.html
